当前位置: 代码迷 >> 综合 >> UOJ #128 [NOI2015 D1T2] 软件包管理器
  详细解决方案

UOJ #128 [NOI2015 D1T2] 软件包管理器

热度:32   发布时间:2024-01-19 01:45:58.0

Linux 用户和 OS X 用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu 使用的 apt-get,Fedora/CentOS 使用的 yum,以及 OS X 下可用的 homebrew 都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包  A A 依赖软件包  B B,那么安装软件包  A A 以前,必须先安装软件包  B B。同时,如果想要卸载软件包  B B,则必须卸载软件包  A A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除  0 0 号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而  0 0 号软件包不依赖任何一个软件包。依赖关系不存在环(若有  m m  (m2) (m≥2) 个软件包  A1,A2,A3,,Am A1,A2,A3,…,Am,其中  A1 A1 依赖  A2 A2 A2 A2 依赖  A3 A3 A3 A3 依赖  A4 A4,……, Am?1 Am?1 依赖  Am Am,而  Am Am 依赖  A1 A1,则称这  m m 个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为  0 0

输入格式

输入文件的第  1 1 行包含  1 1 个正整数  n n,表示软件包的总数。软件包从  0 0 开始编号。

随后一行包含  n?1 n?1 个整数,相邻整数之间用单个空格隔开,分别表示  1,2,3,,n?2,n?1 1,2,3,…,n?2,n?1 号软件包依赖的软件包的编号。

接下来一行包含  1 1 个正整数  q q,表示询问的总数。

之后  q q 行,每行  1 1 个询问。询问分为两种:

  • install  x x:表示安装软件包  x x
  • uninstall  x x:表示卸载软件包  x x

你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)。

输出格式

输出文件包括  q q 行。

输出文件的第  i i 行输出  1 1 个整数,为第  i i 步操作中改变安装状态的软件包数。

样例一

input
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
output
3
1
3
2
3
explanation

一开始所有的软件包都处于未安装状态。

安装  5 5 号软件包,需要安装  0,1,5 0,1,5 三个软件包。

之后安装  6 6 号软件包,只需要安装  6 6 号软件包。此时安装了  0,1,5,6 0,1,5,6 四个软件包。

卸载  1 1 号软件包需要卸载  1,5,6 1,5,6 三个软件包。此时只有  0 0 号软件包还处于安装状态。

之后安装  4 4 号软件包,需要安装  1,4 1,4 两个软件包。此时  0,1,4 0,1,4 处在安装状态。

最后,卸载  0 0 号软件包会卸载所有的软件包。

样例二

input
10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9
output
1
3
2
1
3
1
1
1
0
1

样例三

见样例数据下载。

限制与约定

测试点编号 n n 的规模 q q 的规模 备注
1 n=5000 n=5000 q=5000 q=5000  
2
3 n=100000 n=100000 q=100000 q=100000 数据不包含卸载操作
4
5 n=100000 n=100000 q=100000 q=100000 编号为  i i 的软件包所依赖的软件包编号在  [0,i?1] [0,i?1] 内均匀随机。
每次执行操作的软件包编号在  [0,n?1] [0,n?1] 内均匀随机。
6
7
8
9 n=100000 n=100000 q=100000 q=100000  
10
11
12
13
14
15
16
17
18
19
20

时间限制: 1s 1s

空间限制: 512MB 512MB

下载

样例数据下载

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

树链剖分+线段树~

我可能是假树链剖分的受害者……第一次知道还能更新子树……

先求出答案,再更新树的标记即可。


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;const int N=100005;int n,m,x,fi[N],w[N],ne[N],fa[N],id[N],dep[N],siz[N],son[N],top[N],cnt,r[N];
char s[20];struct node{int l,r,a,b;
}c[N<<2];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;
}void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;fa[v]=u;
}void dfs(int u)
{siz[u]=1;for(int i=fi[u];i;i=ne[i]){dep[w[i]]=dep[u]+1;dfs(w[i]);siz[u]+=siz[w[i]];if(siz[son[u]]<siz[w[i]]) son[u]=w[i];}
}void dfs1(int u,int la)
{id[u]=++cnt;top[u]=la;if(son[u]){dfs1(son[u],la);for(int i=fi[u];i;i=ne[i])if(w[i]!=son[u]) dfs1(w[i],w[i]);}r[u]=cnt;
}void build(int l,int r,int k)
{c[k].l=l;c[k].r=r;c[k].b=-1;if(l==r) return;int mid=l+r>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);
}void update(int u,int v)
{c[u].a=v*(c[u].r-c[u].l+1);c[u].b=v;
}void pushdown(int u)
{if(c[u].b==-1) return;update(u<<1,c[u].b);update(u<<1|1,c[u].b);c[u].b=-1;
}int cal(int k,int u,int v)
{int l=c[k].l,r=c[k].r,mid=l+r>>1,now=0;if(l>=u && r<=v) return c[k].a;pushdown(k);if(u<=mid) now+=cal(k<<1,u,v);if(v>mid) now+=cal(k<<1|1,u,v);return now;
}void chan(int k,int u,int v,int kkz)
{int l=c[k].l,r=c[k].r,mid=l+r>>1;if(l>=u && r<=v){update(k,kkz);return;}pushdown(k);if(u<=mid) chan(k<<1,u,v,kkz);if(v>mid) chan(k<<1|1,u,v,kkz);c[k].a=c[k<<1].a+c[k<<1|1].a; 
}int cal_add(int u)
{int now=0;while(top[u]!=1){now+=cal(1,id[top[u]],id[u]);u=fa[top[u]];}return now+cal(1,1,id[u]);
}int sol_chan(int u)
{int v=1,now=0;while(top[u]!=1){chan(1,id[top[u]],id[u],1);u=fa[top[u]];}chan(1,1,id[u],1);
}int main()
{n=read();for(int i=2;i<=n;i++) x=read()+1,add(x,i);dep[1]=1;cnt=0;dfs(1);dfs1(1,1);build(1,n,1);m=read();while(m--){scanf("%s",s);x=read()+1;if(s[0]=='i'){printf("%d\n",dep[x]-cal_add(x));sol_chan(x);}else{printf("%d\n",cal(1,id[x],r[x]));chan(1,id[x],r[x],0);}}return 0;
}