bzoj3731: Gty的超级妹子树（树分块）

传送门

分块树，代码参考了Manchery的

具体细节还是看代码好了

这题卡常……注意常数写好点……

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 struct Block{

     vector<int> a;

     inline void insert(int x){

         a.insert(lower_bound(a.begin(),a.end(),x+),x);

     }

     inline void erase(int x){

         a.erase(lower_bound(a.begin(),a.end(),x));

     }

     inline void modify(int x,int y){

         erase(x),insert(y);

     }

     inline int query(int x){

         return a.end()-upper_bound(a.begin(),a.end(),x);

     }

     inline int size(){return a.size();}

 }Blo[N];

 int tot,ver[N<<],head[N],Next[N<<],first[N];

 inline void add(int u,int v){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;

 }

 inline void addb(int u,int v){

     ver[++tot]=v,Next[tot]=first[u],first[u]=tot;

 }

 int n,B,a[N],fa[N],belong[N],bat[N],cnt;

 void dfs(int u,int f){

     fa[u]=f;

     if(u==||Blo[belong[f]].size()==B)

     Blo[belong[u]=++cnt].insert(a[u]),addb(belong[f],belong[u]),bat[cnt]=belong[f];

     else Blo[belong[u]=belong[f]].insert(a[u]);

     for(int i=head[u];i;i=Next[i])

     if(ver[i]!=f) dfs(ver[i],u);

 }

 int Y,ans=;

 void block_dfs(int u){

     ans+=Blo[u].query(Y);

     for(int i=first[u];i;i=Next[i])

     if(bat[ver[i]]==u) block_dfs(ver[i]);

 }

 void find(int u,int f){

     if(a[u]>Y) ++ans;

     for(int i=head[u];i;i=Next[i])

     if(ver[i]!=f&&fa[ver[i]]==u)

     if(belong[ver[i]]==belong[u]) find(ver[i],u);

     else block_dfs(belong[ver[i]]);

 }

 int c[N],d[N];

 void cont(int u,int f){

     c[++*c]=u;

     for(int i=head[u];i;i=Next[i])

     if(ver[i]!=f&&fa[ver[i]]==u)

     if(belong[ver[i]]==belong[u]) cont(ver[i],u);

     else d[++*d]=belong[ver[i]];

 }

 int main(){

     int q,op,u,v,lastans=;

     //freopen("testdata.in","r",stdin);

     n=read(),B=sqrt(n);

     for(int i=;i<n;++i)

     u=read(),v=read(),add(u,v),add(v,u);

     for(int i=;i<=n;++i) a[i]=read();

     dfs(,);q=read();

     while(q--){

         op=read();

         switch(op){

             case :{

                 u=read(),v=read();

                 u^=lastans,v^=lastans;

                 Y=v,ans=;

                 find(u,fa[u]);

                 printf("%d\n",lastans=ans);

                 break;

             }

             case :{

                 u=read(),v=read();

                 u^=lastans,v^=lastans;

                 Blo[belong[u]].modify(a[u],v);

                 a[u]=v;

                 break;

             }

             case :{

                 u=read(),v=read();

                 u^=lastans,v^=lastans;

                 a[++n]=v;

                 add(u,n),add(n,u);

                 fa[n]=u;

                 if(Blo[belong[u]].size()==B)

                 Blo[belong[n]=++cnt].insert(a[n]),addb(belong[u],belong[n]),bat[cnt]=belong[u];

                 else Blo[belong[n]=belong[u]].insert(a[n]);

                 break;

             }

             case :{

                 u=read(),u^=lastans;

                 if(belong[u]!=belong[fa[u]]){

                     fa[u]=,bat[belong[u]]=;break;

                 }

                 cont(u,fa[u]);

                 belong[u]=++cnt;

                 for(int i=;i<=*c;++i){

                     Blo[belong[fa[u]]].erase(a[c[i]]);

                     Blo[cnt].insert(a[c[i]]);

                     belong[c[i]]=cnt;

                 }

                 for(int i=;i<=*d;++i)

                 addb(cnt,d[i]),bat[d[i]]=cnt;

                 fa[u]=,*c=*d=;

                 break;

             }

         }

     }

     return ;

 }