BZOJ4196: [Noi2015]软件包管理器

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c==‘-‘) f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-‘0‘;
    return x*f;
}
const int maxn=100010;
int n,e,first[maxn],next[maxn],to[maxn];
void AddEdge(int u,int v) {to[++e]=v;next[e]=first[u];first[u]=e;}
int fa[maxn],dep[maxn],siz[maxn],son[maxn],top[maxn],L[maxn],R[maxn],ToT;
void dfs(int x) {
    siz[x]=1;
    ren {
        dep[to[i]]=dep[x]+1;dfs(to[i]);siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
    }
}
void build(int x,int tp) {
    top[x]=tp;L[x]=++ToT;
    if(son[x]) build(son[x],tp);
    ren if(to[i]!=son[x]) build(to[i],to[i]);
    R[x]=ToT;
}
int sumv[maxn<<2],setv[maxn<<2];
int update(int o,int l,int r,int ql,int qr,int tp) {
    int ans=0;
    if(ql<=l&&r<=qr) {
        ans=tp?r-l+1-sumv[o]:sumv[o];
        setv[o]=tp;sumv[o]=tp*(r-l+1);
    }
    else {
        int mid=l+r>>1,lc=o<<1,rc=lc|1;
        if(setv[o]>=0) {
            setv[lc]=setv[rc]=setv[o];
            sumv[lc]=setv[o]*(mid-l+1);
            sumv[rc]=setv[o]*(r-mid);
            setv[o]=-1;
        }
        if(ql<=mid) ans+=update(lc,l,mid,ql,qr,tp);
        if(qr>mid) ans+=update(rc,mid+1,r,ql,qr,tp);
        sumv[o]=sumv[lc]+sumv[rc];
    }
    return ans;
}
int query(int x) {
    int f=top[x],ans=0;
    while(f!=1) {
        ans+=update(1,1,n,L[f],L[x],1);
        x=fa[f];f=top[x];
    }
    return ans+update(1,1,n,1,L[x],1);
}
int main() {
    memset(setv,-1,sizeof(setv));
    n=read();rep(i,2,n) AddEdge(fa[i]=read()+1,i);
    dfs(1);build(1,1);
    dwn(T,read(),1) {
        char t=Getchar();
        while(!isalpha(t)) t=Getchar();
        if(t==‘i‘) printf("%d\n",query(read()+1));
        else {
            int x=read()+1;
            printf("%d\n",update(1,1,n,L[x],R[x],0));
        }
    }
    return 0;
}