Description
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Input
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
Solution
这题是LCT的巧妙应用。把给出的数据当做森林，即i的父亲是i+k[i]，询问的是到根的路径长度+1，可以修改父亲。所以只需要link操作即可，注意把超过n的节点设为0。每次询问先access，然后Splay到根（Splay中要维护size），这样所询问的答案就是节点在Splay上的左子树大小+1。
代码：
3
Solution
这题是LCT的巧妙应用。把给出的数据当做森林，即i的父亲是i+k[i]，询问的是到根的路径长度+1，可以修改父亲。所以只需要link操作即可，注意把超过n的节点设为0。每次询问先access，然后Splay到根（Splay中要维护size），这样所询问的答案就是节点在Splay上的左子树大小+1。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;inline int read(){int xx=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())xx=xx*10+ch-'0';return xx*f;
}const int maxn=200010;
struct node{int fa,ch[2],size;bool is_root;
}T[maxn];
int n,m,k[maxn];void update(int x){T[x].size=1;if(T[x].ch[0])T[x].size+=T[T[x].ch[0]].size;if(T[x].ch[1])T[x].size+=T[T[x].ch[1]].size;
}
int getson(int x){return x==T[T[x].fa].ch[1];
}
void rotate(int x){if(T[x].is_root)return;int k=getson(x),fa=T[x].fa;int fafa=T[fa].fa;T[fa].ch[k]=T[x].ch[k^1];if(T[x].ch[k^1])T[T[x].ch[k^1]].fa=fa;T[x].ch[k^1]=fa;T[fa].fa=x;T[x].fa=fafa;if(!T[fa].is_root)T[fafa].ch[fa==T[fafa].ch[1]]=x;else T[x].is_root=true,T[fa].is_root=false;update(fa);update(x);
}
void Splay(int x){for(int fa;!T[x].is_root;rotate(x)){if(!T[fa=T[x].fa].is_root){rotate((getson(x)==getson(fa))?fa:x);}}
}
void access(int x){int y=0;do{Splay(x);T[T[x].ch[1]].is_root=true;T[T[x].ch[1]=y].is_root=false;update(x);x=T[y=x].fa;}while(x);
}
void link(int u,int v){if(v>n)v=0;access(u);Splay(u);T[T[u].ch[0]].is_root=true;T[T[u].ch[0]].fa=0;T[u].ch[0]=0;T[u].fa=v;update(u);
}
int Query(int x){access(x);Splay(x);return T[T[x].ch[0]].size+1;
}
void Work(){int opt,x,y;while(m--){opt=read();x=read();if(opt==1)printf("%d\n",Query(x+1));else if(opt==2){y=read();link(x+1,x+y+1);}}
}int main(){n=read();for(int i=1;i<=n;i++){T[i].is_root=T[i].size=1;T[i].fa=T[i].ch[0]=T[i].ch[1]=0;}for(int i=1;i<=n;i++){k[i]=read();link(i,i+k[i]);}m=read();Work();return 0;
}