当前位置 博文首页 > weixin_34417183的博客:bzoj4196
开始看lct后觉得链剖真是很水。。。
1 #include<bits/stdc++.h> 2 #define lowbit(a) ((a)&(-(a))) 3 #define l(a) ((a)<<1) 4 #define r(a) ((a)<<1|1) 5 #define clr(a,x) memset(a,x,sizeof(a)) 6 #define rep(i,l,r) for(int i=l;i<(r);i++) 7 #define Rep(i,a) rep(i,0,e[a].size()) 8 typedef long long ll; 9 using namespace std; 10 int read() 11 { 12 char c=getchar(); 13 int ans=0,f=1; 14 while(!isdigit(c)){ 15 if(c=='-') f=-1; 16 c=getchar(); 17 } 18 while(isdigit(c)){ 19 ans=ans*10+c-'0'; 20 c=getchar(); 21 } 22 return ans*f; 23 } 24 struct node{ 25 int l,r,sum,set; 26 }; 27 const int maxn=100009,inf=0x3fffffff; 28 int ans,n,m,dfstime=0,size[maxn],top[maxn],son[maxn],dep[maxn],f[maxn],L[maxn],R[maxn],id[maxn]; 29 node x[maxn<<2]; 30 vector<int>e[maxn]; 31 void dfs(int k){ 32 size[k]=1; 33 Rep(i,k){ 34 int to=e[k][i]; 35 if(f[k]==to) continue; 36 dep[to]=dep[k]+1; 37 f[to]=k; 38 dfs(to); 39 size[k]+=size[to]; 40 if(!son[k]||size[son[k]]<size[to]) son[k]=to; 41 } 42 } 43 int Top; 44 void Dfs(int k){ 45 top[k]=Top; 46 L[k]=id[k]=++dfstime; 47 if(son[k]) Dfs(son[k]); 48 Rep(i,k){ 49 int to=e[k][i]; 50 if(id[to]) continue; 51 Dfs(Top=to); 52 } 53 R[k]=dfstime; 54 } 55 void pushdown(int k){ 56 if(x[k].set&&x[k].l!=x[k].r){ 57 x[l(k)].sum=x[k].set==1?x[l(k)].r-x[l(k)].l+1:0; 58 x[r(k)].sum=x[k].set==1?x[r(k)].r-x[r(k)].l+1:0; 59 x[l(k)].set=x[k].set; 60 x[r(k)].set=x[k].set; 61 } 62 x[k].set=0; 63 } 64 void maintain(int k){ 65 x[k].sum=x[l(k)].sum+x[r(k)].sum; 66 } 67 void modify(int k,int l,int r,int t){ 68 pushdown(k); 69 if(x[k].l==l&&x[k].r==r){ 70 if(t==1) ans+=r-l+1-x[k].sum; 71 else ans+=x[k].sum; 72 x[k].sum=t==1?r-l+1:0; 73 x[k].set=t; 74 return; 75 } 76 int mid=(x[k].l+x[k].r)>>1; 77 if(r<=mid) modify(l(k),l,r,t); 78 else if(l>mid) modify(r(k),l,r,t); 79 else{ 80 modify(l(k),l,mid,t); 81 modify(r(k),mid+1,r,t); 82 } 83 maintain(k); 84 } 85 void build(int k,int l,int r){ 86 x[k].l=l,x[k].r=r,x[k].sum=x[k].set=0; 87 if(l==r) return; 88 int mid=(l+r)>>1; 89 build(l(k),l,mid); 90 build(r(k),mid+1,r); 91 maintain(k); 92 } 93 void install(int u,int v){ 94 while(top[u]!=top[v]){ 95 if(dep[top[u]]<dep[top[v]]) swap(u,v); 96 modify(1,id[top[u]],id[u],1); 97 u=f[top[u]]; 98 } 99 if(dep[u]>dep[v]) swap(u,v); 100 modify(1,id[u],id[v],1); 101 } 102 void init(){ 103 dfs(0); 104 Dfs(Top=0); 105 build(1,1,n); 106 } 107 int main() 108 { 109 n=read(); 110 rep(i,1,n){ 111 int to=read(); 112 e[i].push_back(to); 113 e[to].push_back(i); 114 } 115 init(); 116 m=read(); 117 while(m--){ 118 char opt=getchar(); 119 while(opt!='i'&&opt!='u') opt=getchar(); 120 int x=read(); 121 ans=0; 122 if(opt=='i'){ 123 install(0,x); 124 printf("%d\n",ans); 125 }else{ 126 modify(1,L[x],R[x],-1); 127 printf("%d\n",ans); 128 } 129 } 130 return 0; 131 }cs