1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 struct node{int ch[2],fa,siz;bool rev;}; 5 node sp[200005]; 6 int n,op,fa[200005]; 7 bool isro(int x){return x!=sp[sp[x].fa].ch[0]&&x!=sp[sp[x].fa].ch[1];} 8 void pushup(int x){sp[x].siz=sp[sp[x].ch[0]].siz+sp[sp[x].ch[1]].siz+1;}; 9 void pushdown(int);10 void Pushdown(int);11 void rot(int);12 void splay(int);13 void access(int);14 void maker(int x){access(x);splay(x);sp[x].rev^=1;}15 void link(int x,int y){maker(x);sp[x].fa=y;splay(x);}16 void cut(int x,int y){maker(x);access(y);splay(y);sp[y].ch[0]=sp[x].fa=0;}17 int main()18 {19     scanf("%d",&n);20     int i,p,x,y;21     for(i=1;i<=n;i++)22     {23         scanf("%d",&p);24         fa[i]=sp[i].fa = min(i+p,n+1);25         sp[i].siz = 1;26     }27     sp[n+1].siz = 1;28     scanf("%d",&op);29     for(i=1;i<=op;i++)30     {31         scanf("%d%d",&p,&x); x++;32         if(p==1)33         {34             maker(n+1);35             access(x);splay(x);36             printf("%d\n",sp[sp[x].ch[0]].siz);37         }38         else39         {40             scanf("%d",&y);41             cut(x,fa[x]);42             link(x,min(n+1,y+x));43             fa[x] = min(n+1,y+x);44         }45     }46     return 0;47 }48 void rot(int now)49 {50     int fa=sp[now].fa;int fafa=sp[fa].fa; bool isr=(now==sp[fa].ch[1]);51     if(!isro(fa)){sp[fafa].ch[fa==sp[fafa].ch[1]]=now;}52     sp[now].fa = fafa;53     sp[fa].ch[isr] = sp[now].ch[!isr];54     sp[sp[now].ch[!isr]].fa = fa;55     sp[now].ch[!isr] = fa;sp[fa].fa = now;56     pushup(fa); pushup(now);57 }58 void pushdown(int now)59 {60     if(sp[now].rev)61     {62         int lc = sp[now].ch[0],rc=sp[now].ch[1];63         if(lc) sp[lc].rev^=1;64         if(rc) sp[rc].rev^=1;65         sp[now].ch[0]=rc,sp[now].ch[1]=lc;66         sp[now].rev = false;67     }68 }69 void Pushdown(int now)70 {71     if(!isro(now)) Pushdown(sp[now].fa);72     pushdown(now);73 } 74 void splay(int now)75 {76     Pushdown(now);77     while(!isro(now))78     {79         if(!isro(sp[now].fa)) rot(now);80         rot(now);81     }82 }83 void access(int x)84 {85     for(int t=0;x;t=x,x=sp[x].fa)86     {87         splay(x);88         sp[x].ch[1] = t;89     }90 }