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的情况，你都要输出一个需要的步数，占一行。
解法二分块见【这里】。
LCT维护，询问的时候先把汇点转到根然后access要询问的节点，splay上维护子树大小。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[200010],son[200010][2],sta[200010],tag[200010],a[200010],size[200010],n,q;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
int isroot(int u)
{return son[fa[u]][0]!=u&&son[fa[u]][1]!=u;
}
void down(int u)
{if (tag[u]){tag[son[u][0]]^=1;tag[son[u][1]]^=1;swap(son[u][0],son[u][1]);tag[u]=0;}
}
void up(int u)
{down(u);size[u]=1;if (son[u][0]) size[u]+=size[son[u][0]];if (son[u][1]) size[u]+=size[son[u][1]];
}
void rot(int u,int x)
{int v=son[u][x],p=son[v][x^1],q=fa[u];if (!isroot(u)) son[q][son[q][1]==u]=v;fa[v]=q;fa[p]=u;son[u][x]=p;son[v][x^1]=u;fa[u]=v;up(u);up(v);up(q);
}
void splay(int u)
{int top=0,v,w,x,y;for (int i=u;;i=fa[i]){sta[++top]=i;if (isroot(i)) break;}for (;top;top--) down(sta[top]);while (!isroot(u)){v=fa[u];x=son[v][1]==u;if (isroot(v)) rot(v,x);else{w=fa[v];y=son[w][1]==v;if (x==y){rot(w,x);rot(v,x);}else{rot(v,x);rot(w,y);}}}
}
void access(int u)
{int v=0;while (u){splay(u);son[u][1]=v;up(u);v=u;u=fa[u];}
}
void makeroot(int u)
{access(u);splay(u);tag[u]^=1;up(u);
}
void link(int u,int v)
{if (v>n) v=n+1;makeroot(u);fa[u]=v;
}
void cut(int u,int v)
{if (v>n) v=n+1;makeroot(u);access(v);splay(v);fa[u]=son[v][0]=0;up(v);
}
int solve(int u)
{makeroot(n+1);access(u);splay(u);return size[u]-1;
}
int main()
{int u,x,opt;n=rd();for (int i=1;i<=n+1;i++) size[i]=1;for (int i=1;i<=n;i++){a[i]=rd();link(i,i+a[i]);}q=rd();while (q--){opt=rd();u=rd();u++;if (opt==1) printf("%d\n",solve(u));else{x=rd();cut(u,u+a[u]);a[u]=x;link(u,u+a[u]);}}
}