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
Sample Output
2
3
题解
首先请大家往上拉回去。看一看加粗了的东西
设弹力系数为x，那么x可以向x+w[x]连边，同理 x+w[x]也可以向x+w[x]+w[x+w[x]]连边…（只要不超边界）
对于超了边界的情况，可以直接x向n+1连边了。。反正这个节点也永远用不到= =
那么可以看出来了，许多条边连起来，最终一定会连向n+1这个节点成为一棵树！问题就转化成了求任意一个节点到根的链的长度
再看一眼题可以发现还有修改弹力系数的操作，这不就是LCT删边插边么
用一个c维护splay里面左孩子家族人数+右孩子家族人数+自己的人数
对于查找x到根n+1的值
首先Mark_root(n+1)，就是让n+1成为动态树的根
然后access(x)，x就和n+1在同一棵splay上了
然后splay(x,0)，让x当根。由于access的操作可以保证x一定在splay最下面，那么旋转上去后就是最上面的了。x~n+1这条链上的节点就是左孩子的c值啦
不会告诉你们这道题在caioj上有双倍经验的
还有诸多类似分块的做法的我就不再概述。
最后一个坑点
节点编号是0~n-1，所以。。输入的时候要x++啊！！！
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct trnode
{int f,son[2],c,n;bool fz;
}tr[210000];
void update(int x)
{int lc=tr[x].son[0],rc=tr[x].son[1];tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}
void reverse(int x)
{tr[x].fz=false;swap(tr[x].son[0],tr[x].son[1]);int lc=tr[x].son[0],rc=tr[x].son[1];tr[lc].fz^=1;tr[rc].fz^=1;
}
void rotate(int x,int w)
{int f=tr[x].f,ff=tr[f].f;int R,r;R=f;r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff;r=x;tr[r].f=R;if(tr[R].son[0]==f)tr[R].son[0]=r;else if(tr[R].son[1]==f)tr[R].son[1]=r;R=x;r=f;tr[R].son[w]=r;tr[r].f=R; update(f);update(x);
}
int tmp[210000];
void splay(int x,int rt)
{int s=0,i=x;while(tr[i].f!=0 && (tr[tr[i].f].son[0]==i || tr[tr[i].f].son[1]==i)){tmp[++s]=i;i=tr[i].f;}tmp[++s]=i;while(s!=0){i=tmp[s--];if(tr[i].fz==true)reverse(i);}while(tr[x].f!=rt && (tr[tr[x].f].son[0]==x || tr[tr[x].f].son[1]==x)){int f=tr[x].f,ff=tr[f].f;if(ff==rt || (tr[ff].son[0]!=f && tr[ff].son[1]!=f)){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f && tr[f].son[0]==x){rotate(f,1);rotate(x,1);}else if(tr[ff].son[0]==f && tr[f].son[1]==x){rotate(x,0);rotate(x,1);}else if(tr[ff].son[1]==f && tr[f].son[1]==x){rotate(f,0);rotate(x,0);}else {rotate(x,1);rotate(x,0);}}}
}
void access(int x)
{int y=0;while(x!=0){splay(x,0);tr[x].son[1]=y;if(y!=0)tr[y].f=x;y=x;x=tr[x].f;}
}
void mark_root(int x)
{access(x);splay(x,0);tr[x].fz^=1;
}
void link(int x,int y)
{mark_root(x);tr[x].f=y;access(x);
}
void cut(int x,int y)
{mark_root(x);access(y);splay(y,0);tr[tr[y].son[0]].f=0;tr[y].son[0]=0;update(y);
}
int find_root(int x)
{access(x);splay(x,0);while(tr[x].son[0]!=0)x=tr[x].son[0];return x;
}
int w[210000];
int n,m,x,y;
int Far(int x)
{mark_root(n+1);access(x);splay(x,0);return tr[tr[x].son[0]].c;
}
void build_tree()
{for(int i=1;i<=n+1;i++){tr[i].f=0;tr[i].c=tr[i].n=1;tr[i].son[0]=tr[i].son[1]=0;tr[i].fz=false;}
}
int main()
{scanf("%d",&n);build_tree();for(int i=1;i<=n;i++){scanf("%d",&w[i]);if(i+w[i]<=n)link(i,i+w[i]);else link(i,n+1);}scanf("%d",&m);while(m--){int op;scanf("%d",&op);if(op==1){scanf("%d",&x);x++;printf("%d\n",Far(x));}else{scanf("%d%d",&x,&y);x++;if(x+w[x]<=n)cut(x,x+w[x]);else cut(x,n+1);w[x]=y;if(x+w[x]<=n)link(x,x+w[x]);else link(x,n+1);}}return 0;
}