「LOJ 2130」「NOI2015」软件包管理器

发表于

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

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 AA 依赖软件包 BB，那么安装软件包 AA 以前，必须先安装软件包 BB。同时，如果想要卸载软件包 BB，则必须卸载软件包 AA。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 00 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 00 号软件包不依赖任何一个软件包。依赖关系不存在环，当然也不会有一个软件包依赖自己。

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

Constraints

n,q≤100000n,q \le 100000

Solution

直接树链剖分然后上线段树。需要维护几个操作：查询子树有效节点数，查询到根节点路径上的有效节点数，子树区间赋值，到根节点路径区间赋值。

时间复杂度 O(nlog2n)O(nlog^2n) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define lc (x<<1)
#define rc (x<<1|1)
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,cnt,L,R,val,ans,dfn,x;
int fa[N],first[N],deep[N];
int tp[N],son[N],sz[N],in[N],out[N];
int s[N*4],tag[N*4];
char op[10];
struct edge{int to,next;}e[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void dfs1(int x)
{
	sz[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		deep[to]=deep[x]+1;
		dfs1(to);sz[x]+=sz[to];
		if(sz[to]>sz[son[x]])son[x]=to;
	}
}
void dfs2(int x,int top)
{
	in[x]=++dfn;tp[x]=top;
	if(!son[x]){out[x]=dfn;return;}
	dfs2(son[x],top);
	for(int i=first[x];i;i=e[i].next)
		if(e[i].to!=son[x])dfs2(e[i].to,e[i].to);
	out[x]=dfn;
}
void down(int x,int l,int r)
{
	int mid=(l+r)>>1,t=tag[x];
	if(t==-1)return;tag[x]=-1;
	s[lc]=(mid-l+1)*t;tag[lc]=t;
	s[rc]=(r-mid)*t;tag[rc]=t;
}
void modify(int x,int l,int r)
{
	if(L<=l&&r<=R){s[x]=(r-l+1)*val;tag[x]=val;return;}
	down(x,l,r);int mid=(l+r)>>1;
	if(L<=mid)modify(lc,l,mid);
	if(R>mid)modify(rc,mid+1,r);
	s[x]=s[lc]+s[rc];
}
void query(int x,int l,int r)
{
	if(L<=l&&r<=R){ans+=s[x];return;}
	down(x,l,r);int mid=(l+r)>>1;
	if(L<=mid)query(lc,l,mid);
	if(R>mid)query(rc,mid+1,r);
}
void change(int x)
{
	while(tp[x]!=1)
	{
		L=in[tp[x]];R=in[x];val=1;
		modify(1,1,n);x=fa[tp[x]];
	}
	L=in[1];R=in[x];val=1;
	modify(1,1,n);x=fa[tp[x]];
}
int ask(int x)
{
	int cur=0;
	while(tp[x]!=1)
	{
		L=in[tp[x]];R=in[x];ans=0;
		query(1,1,n);cur+=ans;x=fa[tp[x]];
	}
	L=in[1];R=in[x];ans=0;
	query(1,1,n);cur+=ans;x=fa[tp[x]];
	return cur;
}
int main()
{
	n=read();
	for(int i=2;i<=n;i++)
		fa[i]=read()+1,ins(fa[i],i);
	deep[1]=1;dfs1(1);dfs2(1,1);
	memset(tag,-1,sizeof(tag));
	m=read();
	while(m--)
	{
		scanf("%s",op);x=read()+1;
		if(op[0]=='u')
		{
			L=in[x];R=out[x];ans=0;
			query(1,1,n);printf("%d\n",ans);
			val=0;modify(1,1,n);
		}
		else
		{
			printf("%d\n",deep[x]-ask(x));
			change(x);
		}
	}
	return 0;
}