【bzoj2002】[Hnoi2010]Bounce 弹飞绵羊 link-cut-tree

 #include<bits/stdc++.h>

 #define N 200005

 using namespace std;

 int read(){

   int x=,f=;char ch=getchar();

   while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

   while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

   return x*f;

 }

 int n,m,next[N];

 namespace LCT{

   int ch[N][],fa[N],sz[N];bool rev[N];

   inline bool isroot(int x){

     if(ch[fa[x]][]!=x&&ch[fa[x]][]!=x)return ;return ;

   }

   inline void pushdown(int x){

     if(rev[x]){

       rev[ch[x][]]^=;rev[ch[x][]]^=;rev[x]=;

       swap(ch[x][],ch[x][]);

     }

   }

   inline void pushup(int x){

     sz[x]=sz[ch[x][]]+sz[ch[x][]]+;

   }

   void rotate(int x){

     int y=fa[x],k=ch[y][]==x;

     if(!isroot(y))ch[fa[y]][ch[fa[y]][]==y]=x;

     fa[x]=fa[y];

     fa[ch[x][!k]]=y;

     fa[y]=x;

     ch[y][k]=ch[x][!k];

     ch[x][!k]=y;

     pushup(y);pushup(x);

   }

   void Pushdown(int x){

     if(!isroot(x))Pushdown(fa[x]);

     pushdown(x);

   }

   void splay(int x){

       Pushdown(x);

       for(int y=fa[x];!isroot(x);y=fa[x]){

         if(!isroot(y)){

             if((ch[fa[y]][ch[fa[y]][]==y])!=(ch[y][]==x))rotate(x);

             else rotate(y);

         }rotate(x);

     }

   }

   inline void access(int x){

     int y=;

     while(x){

       splay(x);

       ch[x][]=y;

       x=fa[y=x];

     }

   }

   inline void moveroot(int x){

     access(x);splay(x);rev[x]^=;

   }

   inline void link(int x,int y){

       moveroot(x);fa[x]=y;splay(x);

   }

   inline void cut(int x,int y){

       moveroot(x);access(y);splay(y);ch[y][]=fa[x]=;

   }

   inline int query(int x){

       moveroot(n+);access(x);splay(x);

       return sz[ch[x][]];

   }

 }

 int main(){

   n=read();

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

     int x=read();

     LCT::fa[i]=x+i;LCT::sz[i]=;

     if(LCT::fa[i]>n)LCT::fa[i]=n+;

     next[i]=LCT::fa[i];

   }

   m=read();

   while(m--){

     int t=read();

     if(t==)printf("%d\n",LCT::query(read()+));

     else {

       int x=read(),y=read();x++;

       int t=min(n+,x+y);

       LCT::cut(x,next[x]);LCT::link(x,t);next[x]=t;

     }

   }

   return ;

 }