树链剖分
带区间修改线段树
install操作：该点到根之间修改成1
uni操作：该点及其子树修改成0
每次操作时和上次的相减一下即可
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> using namespace std; template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;} template <typename T> inline T max(T &a,T &b) {return a>b ?a:b;} template <typename T> inline void read(T &x){ char c=getchar(); x=0; bool f=1; while(!isdigit(c)) f= !f||c=='-' ? 0:1,c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); x= f ? x:-x; } template <typename T> inline void output(T x){ if(!x) {putchar(48); return ;} if(x<0) putchar('-'),x=-x; int wt[50],l=0; while(x) wt[++l]=x%10,x/=10; while(l) putchar(wt[l--]+48); } typedef int arr[100003]; int n,m,cnt,tot; char opt[15]; arr d,fa,siz,bgs,tp,id,hd,ed; int nxt[200003],poi[200003],sum[400003],tag[400003]; inline void add_(int x,int y){ nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt; ed[x]=cnt; poi[cnt]=y; } inline void pushdown(int o,int l,int r){ if(tag[o]==-1) return ; //没标记要跳出 int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); sum[lc]=tag[o]*(mid-l+1); sum[rc]=tag[o]*(r-mid); tag[lc]=tag[o]; tag[rc]=tag[o]; tag[o]=-1; } inline void build(int o,int l,int r){ if(l==r) {sum[o]=0; return;} int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); build(lc,l,mid); build(rc,mid+1,r); } inline int update(int o,int l,int r,int x1,int x2,int v){ int res=0; if(x1<=l&&r<=x2){ if(v) res=r-l+1-sum[o],sum[o]=r-l+1,tag[o]=1; else res=sum[o],sum[o]=tag[o]=0; return res; }pushdown(o,l,r); int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); if(x1<=mid) res+=update(lc,l,mid,x1,x2,v); if(x2>mid) res+=update(rc,mid+1,r,x1,x2,v); sum[o]=sum[lc]+sum[rc]; return res; } inline bool if_del(int o,int l,int r,int x){ if(l==r) return tag[o]!=1; pushdown(o,l,r); int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); if(x<=mid) return if_del(lc,l,mid,x); else return if_del(rc,mid+1,r,x); } inline void dfs1(int x,int _fa){ d[x]=d[_fa]+1,fa[x]=_fa,siz[x]=1; for(int i=hd[x];i;i=nxt[i]) if(poi[i]!=_fa){ dfs1(poi[i],x); siz[x]+=siz[poi[i]]; if(siz[bgs[x]]<siz[poi[i]]) bgs[x]=poi[i]; } } inline void dfs2(int x,int _top){ id[x]=++tot,tp[x]=_top; if(siz[x]==1) return; dfs2(bgs[x],_top); for(int i=hd[x];i;i=nxt[i]) if(poi[i]!=fa[x]&&poi[i]!=bgs[x]) dfs2(poi[i],poi[i]); } inline int ins(int x){ int res=0; while(if_del(1,1,n,id[tp[x]])){ //要调用id映射！！！！！！（-1h） res+=update(1,1,n,id[tp[x]],id[x],1); if(!fa[tp[x]]) return res; x=fa[tp[x]]; }//优化：向上跳直到第一个值为1的点 return res+update(1,1,n,id[tp[x]],id[x],1); } int main(){ read(n); int q; for(int i=1;i<n;++i) read(q),add_(i+1,q+1),add_(q+1,i+1); dfs1(1,0); dfs2(1,1); build(1,1,n); read(m); for(int i=1;i<=m;++i){ scanf("%s",opt); read(q),++q; if(opt[0]=='i') output(ins(q)); else output(update(1,1,n,id[q],id[q]+siz[q]-1,0)); putchar(' '); }return 0; }