【NOI2015】软件包管理器

Description

你决定设计你自己的软件包管理器。不可避免的，你要解决软件包之间的依赖关系。如果A依赖B，那么安装A之前需安装B，卸载B之前须卸载A。0号软件包不依赖任何软件包。依赖关系不存在环(包括自环)。
你的任务是，求出每次安装、删除操作会改变多少个包的状态。
安装一个已安装的软件包，或者卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0
每次操作不仅需要计算安装软件包数，还作为操作影响后来的安装/删除

Input

第一行一个整数n,表示软件包的总数。
随后n-1个整数a1,a2,...an-1，表示第i个软件包依赖第ai个软件包
接下来一行一个整数q,表示询问数
之后q行，每行一个询问，询问分为两种
install x：表示安装x
uninstall x：表示卸载x

Output

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

Sample Input

样例输入1： 

7 

0 0 0 1 1 5 

5 

install 5 

install 6 

uninstall 1 

install 4 

uninstall 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

Sample Output

样例输出1： 











样例输出2： 



















1

Hint

样例输入1说明：

一开始所有的软件包都处于未安装状态。
安装5号软件包，需安装0,1,5三个软件包
之后安装6号软件包，只需安装6号软件包。此时安装了0,1,5,6四个软件包。
卸载1号软件包需要卸载1,5,6三个软件包，此时只有0号软件包还处于安装状态
之后安装4号软件包，需安装1,4两个软件包。此时0,1,4处于安装状态
最后，卸载0号软件包会卸载所有的软件包

数据提示：
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 不随机

Source

NOI2015 Day1 T2
树链剖分

思路{

　　树链剖分题。

　　安装和非安装可看成0,1串，查询区间和即可

}

  1 #include<algorithm>
  2 
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<vector>
  7 #include<queue>
  8 #include<ctime>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 #define MAXX 1000010
 13 #define rs ((o<<1)|1)
 14 #define ls (o<<1)
 15 #define mid ((l+r)>>1)
 16 using namespace std;
 17 struct ed{
 18   int nxt,to;
 19 }e[MAXX*2];
 20 int tot,sum,n,m,q,lazy[MAXX*4],x;
 21 char a[50];
 22 int tree[MAXX*4],deep[MAXX],siz[MAXX+10],hson[MAXX],head[MAXX],top[MAXX],id[MAXX],fa[MAXX],tt[MAXX];
 23 void addd(int u,int v){e[tot].nxt=head[u],e[tot].to=v,head[u]=tot++;}
 24 void ADD(int u,int v){addd(u,v),addd(v,u);}
 25 void dfs1(int u,int faa){
 26   fa[u]=faa,deep[u]=deep[faa]+1,siz[u]=1;
 27   for(int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=faa){
 28       int v=e[i].to;dfs1(v,u);
 29       siz[u]+=siz[v];
 30       if(siz[hson[u]]<siz[v]||!hson[u])hson[u]=v;
 31     }
 32 }
 33 void dfs2(int u,int toop){
 34   id[u]=++sum;top[u]=toop;if(hson[u]!=MAXX+8)dfs2(hson[u],toop);
 35   for(int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=hson[u]&&e[i].to!=fa[u])dfs2(e[i].to,e[i].to);
 36   tt[u]=sum;
 37 }
 38 void down(int o,int l,int r){
 39   if(!lazy[o])return;
 40   if(lazy[o]==1)tree[ls]=(mid-l+1),tree[rs]=(r-mid);
 41   else if(lazy[o]==-1)tree[ls]=tree[rs]=0;
 42   lazy[rs]=lazy[ls]=lazy[o];lazy[o]=0;
 43 }
 44 int ask(int o,int l,int r,int ll,int rr){
 45   if(l!=r)down(o,l,r);
 46   if(l>=ll&&r<=rr)return tree[o];
 47   if(mid<ll)return ask(rs,mid+1,r,ll,rr);
 48   else if(mid>=rr)return ask(ls,l,mid,ll,rr);
 49   else return ask(rs,mid+1,r,ll,rr)+ask(ls,l,mid,ll,rr);
 50 }
 51 void change(int o,int l,int r,int ll,int rr){
 52   if(l!=r)down(o,l,r);
 53   if(l>=ll&&r<=rr){tree[o]=r-l+1;lazy[o]=1;return;}
 54   if(mid<ll)change(rs,mid+1,r,ll,rr);
 55   else if(mid>=rr)change(ls,l,mid,ll,rr);
 56   else change(rs,mid+1,r,ll,rr),change(ls,l,mid,ll,rr);
 57   tree[o]=tree[rs]+tree[ls];
 58 }
 59 int lca(int x,int y){
 60   int sum=0;
 61   while(top[x]!=top[y]){
 62     if(deep[top[x]]<deep[top[y]])swap(x,y);
 63     sum+=id[x]-id[top[x]]-ask(1,1,n,id[top[x]],id[x])+1;
 64     change(1,1,n,id[top[x]],id[x]);
 65     x=fa[top[x]];
 66   }
 67   if(deep[x]>deep[y])swap(x,y);
 68   sum+=id[y]-id[x]+1-ask(1,1,n,id[x],id[y]);
 69   change(1,1,n,id[x],id[y]);
 70   return sum;
 71 }
 72 int ask1(int o,int l,int r,int ll,int rr){
 73   if(l!=r)down(o,l,r);
 74   if(l>=ll&&r<=rr)return tree[o];
 75   if(mid<ll)return ask1(rs,mid+1,r,ll,rr);
 76   else if(mid>=rr)return ask1(ls,l,mid,ll,rr);
 77   else return ask1(rs,mid+1,r,ll,rr)+ask1(ls,l,mid,ll,rr);
 78 }
 79 void chage(int o,int l,int r,int ll,int rr){
 80   if(l!=r)down(o,l,r);
 81   if(l>=ll&&r<=rr){
 82     tree[o]=0;lazy[o]=-1;return;
 83   }if(mid<ll)chage(rs,mid+1,r,ll,rr);
 84   else if(mid>=rr)chage(ls,l,mid,ll,rr);
 85   else chage(rs,mid+1,r,ll,rr),chage(ls,l,mid,ll,rr);
 86   tree[o]=tree[ls]+tree[rs];
 87 }
 88 int main(){
 89   memset(head,-1,sizeof(head));
 90   scanf("%d",&n);for(int i=1;i<=n;++i)hson[i]=MAXX+8;
 91   for(int i=1;i<n;++i){int v;scanf("%d",&v);ADD(i,v);}
 92   dfs1(0,0),dfs2(0,0);
 93   scanf("%d",&q);
 94   for(int i=1;i<=q;++i){
 95     scanf("%s",a);scanf("%d",&x);
 96     if(a[0]=='i')printf("%d
",lca(0,x));
 97     else {
 98       printf("%d
",ask1(1,1,n,id[x],tt[x]));
 99       chage(1,1,n,id[x],tt[x]);
100     }
101   }
102   return 0;
103 }