洛谷-P2146- [NOI2015]软件包管理器（树链剖分）

题目链接：https://www.luogu.org/problemnew/show/P2146

题目大意：中文题。给出一些依靠的关系，让你从中得到卸载，安装相关联的软件包个数。

思路：由于0节点是基础包，所以我们可以以0节点为根建一棵树，然后使用树链剖分，即：安装的时候讲0~x这个链全都置为1，卸载的时候将x节点的子树都置为0，每次查询他们之间的差值就是修改软件包的个数。板子，抄上去就行了。因为PushDown()手残写错了导致Debug了一个多小时。QAQ

ACCode：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
  
#include<stdio.h>
#include<string.h> 
#include<math.h> 
   
#include<map>  
#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
#define ll long long 
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ??
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;

class Segment{
    int Tree[MAXN<<2],Lazy[MAXN<<2];
    
    void PushDown(int l,int r,int rt){
        if(Lazy[rt]!=-1){
            int mid=(l+r)>>1;
            Tree[rt<<1]=(mid-l+1)*Lazy[rt];
            Tree[rt<<1|1]=(r-mid)*Lazy[rt];
            Lazy[rt<<1]=Lazy[rt<<1|1]=Lazy[rt];
            Lazy[rt]=-1;
        }
    }
    public :
        void Build(){
            clean(Tree,0);clean(Lazy,-1);
        }
        void Update(int ql,int qr,int val,int l,int r,int rt){
//			cout<<"ql,qr,l,r: "<<ql<<" "<<qr<<" "<<l<<" "<<r<<endl;
            if(ql<=l&&r<=qr){
                Tree[rt]=(r-l+1)*val;Lazy[rt]=val;
//				cout<<"l,r: "<<l<<" "<<r<<endl;
//				cout<<"Tree[rt],val = "<<Tree[rt]<<" "<<val<<" "<<(r-l+1)<<endl;
                return ;
            }
            int mid=(l+r)>>1;
            PushDown(l,r,rt);
            if(ql<=mid) Update(ql,qr,val,l,mid,rt<<1);
            if(qr>mid) Update(ql,qr,val,mid+1,r,rt<<1|1);
            Tree[rt]=Tree[rt<<1]+Tree[rt<<1|1];
        }
        int Query(int ql,int qr,int l,int r,int rt){
//			cout<<"Query:ql,qr: "<<ql<<" "<<qr<<" "<<l<<" "<<r<<" "<<Tree[rt]<<endl;
            if(ql<=l&&r<=qr) return Tree[rt];
            int mid=(l+r)>>1;
            PushDown(l,r,rt);
            int res=0;
            if(ql<=mid) res+=Query(ql,qr,l,mid,rt<<1);
            if(qr>mid) res+=Query(ql,qr,mid+1,r,rt<<1|1);
            return res;
        }
        void Show(int l,int r,int rt){
            printf("l=%d r=%d Tree[rt]=%d\n",l,r,Tree[rt]);
            if(l==r) return ;
            int mid=(l+r)>>1;
            Show(l,mid,rt<<1);Show(mid+1,r,rt<<1|1);
        }
};
struct Node1{
    int v,val,nxt;
    Node1(int _v=0,int _val=0,int _nxt=0){
        v=_v;val=_val;nxt=_nxt;
    }
};
Segment Seg;
Node1 Edge[MAXN<<2];
int Head[MAXN],Ecnt;
int Deep[MAXN],Fa[MAXN],Size[MAXN],Son[MAXN];
int Idx[MAXN],Icnt;
int Top[MAXN];
int n;

void Intt(){
    clean(Head,-1);Ecnt=0;
    clean(Deep,0);clean(Fa,-1);
    clean(Size,0);clean(Son,-1);
    Icnt=0;
}
void AddEdge(int u,int v,int val){
    Edge[Ecnt]=Node1(v,val,Head[u]);
    Head[u]=Ecnt++;
}
int DFS1(int u,int fa,int dep){
    Deep[u]=dep;
    Fa[u]=fa;
    Size[u]=1;
    int maxson=-1;
    for(int i=Head[u];i+1;i=Edge[i].nxt){
        int temp=Edge[i].v;
        if(temp==fa) continue;
        Size[u]+=DFS1(temp,u,dep+1);
        if(Size[temp]>maxson){
            maxson=Size[temp];
            Son[u]=temp;
        }
    }return Size[u];
}
void DFS2(int u,int topfa){
    Idx[u]=++Icnt;
    Top[u]=topfa;
    if(Son[u]==-1) return ;
    DFS2(Son[u],topfa);
    for(int i=Head[u];i+1;i=Edge[i].nxt){
        int temp=Edge[i].v;
        if(Idx[temp]==0){
            DFS2(temp,temp);
        }
    }
}
int QueryPath(int l,int r){
    int ans=0;
    while(Top[l]!=Top[r]){
        if(Deep[Top[l]]<Deep[Top[r]]) swap(l,r);
        ans+=Seg.Query(Idx[Top[l]],Idx[l],1,n,1);
        l=Fa[Top[l]];
    }
    if(Deep[l]>Deep[r]) swap(l,r);
    ans+=Seg.Query(Idx[l],Idx[r],1,n,1);
    return ans;
}
void UpdatePath(int l,int r,int val){
    while(Top[l]!=Top[r]){
        if(Deep[Top[l]]<Deep[Top[r]]) swap(l,r);
//		cout<<"Update: "<<Idx[Top[l]]<<" "<<Idx[l]<<endl;
        Seg.Update(Idx[Top[l]],Idx[l],val,1,n,1);
        l=Fa[Top[l]];
    }
    if(Deep[l]>Deep[r]) swap(l,r);
//	cout<<"Update: "<<Idx[l]<<" "<<Idx[r]<<endl;
    Seg.Update(Idx[l],Idx[r],val,1,n,1);
}
int QuerySubTree(int rt){
    int l=Idx[rt],r=Idx[rt]+Size[rt]-1;
//	cout<<"查询子树："<<l<<" "<<r<<endl;
    int ans=Seg.Query(l,r,1,n,1);
    return ans;
}
void UpdateSubTree(int rt,int val){
    int l=Idx[rt],r=Idx[rt]+Size[rt]-1;
//	cout<<"Delete: "<<l<<" "<<r<<endl;
    Seg.Update(l,r,val,1,n,1);
}
int main(){
    scanf("%d",&n);Intt();
    for(int i=1;i<n;++i){
        int fa;scanf("%d",&fa);
        AddEdge(fa+1,i+1,1);AddEdge(i+1,fa+1,1);
    }DFS1(1,-1,1);DFS2(1,1);
//	for(int i=0;i<n;++i){
//		cout<<"i,Idx,Size: "<<i+1<<" "<<Idx[i+1]<<" "<<Size[i+1]<<endl;
//	}cout<<endl;
    Seg.Build();
    int m;scanf("%d",&m);
    for(int i=1;i<=m;++i){
        char oper[15];int x;
        scanf("%s%d",&oper,&x);
        if(oper[0]=='i'){//安装 
            int have=QueryPath(1,x+1);
            UpdatePath(1,x+1,1);
//			printf("Update:\n");Seg.Show(1,n,1);
            int nowhave=QueryPath(1,x+1);
            printf("%d\n",nowhave-have);
        }
        else{//卸载 
            int have=QuerySubTree(x+1);
            UpdateSubTree(x+1,0);
            int nowhave=QuerySubTree(x+1);
//			cout<<"pre->now: "<<have<<" "<<nowhave<<endl;
            printf("%d\n",have-nowhave);
        }
//		Seg.Show(1,n,1);
    }
    
}