noi2015软件包管理器

本文主要是介绍noi2015软件包管理器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

你决定设计你自己的软件包管理器。不可避免的，你要解决软件包之间的依赖关系。如果A依赖B，那么安装A之前需安装B，卸载B之前须卸载A。0号软件包不依赖任何软件包。依赖关系不存在环(包括自环)。

你的任务是，求出每次安装、删除操作会改变多少个包的状态。

安装一个已安装的软件包，或者卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0

每次操作不仅需要计算安装软件包数，还作为操作影响后来的安装/删除

【输入格式】

第一行一个整数n,表示软件包的总数。

随后n-1个整数 a1,a2,...an−1 ，表示第i个软件包依赖第 ai 个软件包

接下来一行一个整数q,表示询问数

之后q行，每行一个询问，询问分为两种

install x：表示安装x

uninstall x：表示卸载x

【输出格式】

q行，每行一个整数，为第i步操作改变安装状态的软件包数

【样例输入1】

7

0 0 0 1 1 5

5

install 5

install 6

uninstall 1

install 4

uninstall 0

【样例输出1】

3

1

3

2

3

【样例说明1】：

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

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

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

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

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

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

【样例输入2】

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

【样例输出2】

1

3

2

1

3

1

1

1

0

1

【提示】

1,2:n=5000 q=5000

3,4:n=100000 q=100000 没有卸载操作

5,6,7,8 n=100000,q=100000 依赖关系和操作随机

9-20 n=100000,q=100000 不随机

【来源】

NOI2015Day1T2

对于题面的描述的，我们很容易想到它是棵树，并且节点又是1e+5，我们选择用树剖+线段树；

我们维护线段树上每一个点的状态（安装或未安装，安装用1来表示，未安装用-1来表示）和当前节点已被覆盖的点数，未被覆盖的点数可以也维护，也可以用区间长减去已被覆盖节点数，当一个线段树节点被打上安装或未安装标记时，就将答案加上已被覆盖的点数或未被覆盖点数并更新其值（一个为0，另一个为区间长），在拿它来更新父亲节点

所维护的信息，最后输出答案就行。。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAX=100000+10;
int fa[MAX];
int dep[MAX];
int son[MAX]={0};
int top[MAX];
int size[MAX];
int tid[MAX];
int head[MAX]={0};
int to[MAX<<1];
int next[MAX<<1]={0};
int edge=1,tim=0;
int n;
inline void dfs1(int x,int p,int d){
	fa[x]=p;
	dep[x]=d;
	size[x]=1;
	for(int i=head[x];i;i=next[i]){
		int u=to[i];
		if(u!=p){
			dfs1(u,x,d+1);
			size[x]+=size[u];
			if(size[u]>size[son[x]]||!son[x])
				son[x]=u;
		}
	}
}
inline void dfs2(int x,int p){
	tid[x]=++tim;
	top[x]=p;
	if(!son[x])
		return ;
	dfs2(son[x],p);
	for(int i=head[x];i;i=next[i]){
		int u=to[i];
		if(u!=fa[x]&&u!=son[x])
			dfs2(u,u);
	}
}
#define isnum (c>='0'&&c<='9')
inline void read(int& x){
	x=0;
	char c=getchar();
	while(!isnum)
		c=getchar();
	while(isnum){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
}
inline void addedge(int x,int y){
	to[edge]=y,next[edge]=head[x],head[x]=edge++;
	to[edge]=x,next[edge]=head[y],head[y]=edge++;     
}
int isum[MAX<<2]={0},usum[MAX<<2];
int ins[MAX<<2]={0};
int ans;
int l,r;
#define lson o<<1,L,mid
#define rson o<<1|1,mid+1,R
inline void pushup(int o){
	isum[o]=isum[o<<1]+isum[o<<1|1];
	usum[o]=usum[o<<1]+usum[o<<1|1];
}
inline void pushdown(int o,int L,int R){
	int mid=(L+R)>>1;
	if(ins[o]==1){
		isum[o<<1]=(mid-L+1);
		usum[o<<1]=0;
		isum[o<<1|1]=R-mid;
		usum[o<<1|1]=0;
		ins[o<<1]=ins[o];
		ins[o<<1|1]=ins[o];
		ins[o]=0;
	}
	else {
		isum[o<<1]=0;
		usum[o<<1]=mid-L+1;
		isum[o<<1|1]=0;
		usum[o<<1|1]=R-mid;
		ins[o<<1]=ins[o];
		ins[o<<1|1]=ins[o];
		ins[o]=0;
	}
}
inline void build(int o,int L,int R){
	usum[o]=(R-L+1);
	if(L==R){
		return ;
	}
	int mid=(L+R)>>1;
	build(lson);
	build(rson);
	pushup(o);
}
inline void query1(int o,int L,int R){
	if(L>=l&&R<=r){
		ins[o]=1;
		ans+=usum[o];
		usum[o]=0;
		isum[o]=(R-L+1);
		return ;
	}
	else if(L!=R){
		int mid=(L+R)>>1;
		if(ins[o]!=0)
			pushdown(o,L,R);
		if(mid>=l)
			query1(lson);
		if(mid<r)
			query1(rson);
		pushup(o);
	}
}
inline void query2(int o,int L,int R){
	if(L>=l&&R<=r){
		ins[o]=-1;
		ans+=isum[o];
		isum[o]=0;
		usum[o]=(R-L+1);
		return ;
	}
	else if(L!=R){
		if(ins[o]!=0)
			pushdown(o,L,R);
		int mid=(L+R)>>1;
		if(mid>=l)
			query2(lson);
		if(mid<r)
			query2(rson);
		pushup(o);
	}
}
inline void Query1(int x,int y){
	ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		l=tid[top[x]];
		r=tid[x];
		query1(1,1,n);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	l=tid[x],r=tid[y];
	query1(1,1,n);
}
inline void Query2(int x){
	ans=0;
	l=tid[x],r=tid[x]+size[x]-1;
	query2(1,1,n);
}
int main(){
	freopen("manager.in","r",stdin);
	freopen("manager.out","w",stdout);
	read(n);
	int x;
	for(int i=2;i<=n;i++){
		read(x);
		addedge(i,x+1);
	}
	int m;
	read(m);
	dfs1(1,1,1);
	dfs2(1,1);
	build(1,1,n);
	string s;
	for(int i=1;i<=m;i++){
		cin>>s;
		read(x);
		if(s[0]=='i'){
			Query1(1,x+1);
			printf("%d\n",ans);
		}
		else {
			Query2(x+1);
			printf("%d\n",ans);
		}
	}
return 0;
}

这篇关于noi2015软件包管理器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---