某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
输入
一行包含一个整数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
输出
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
样例输入
4
1 2 1 1
3
1 1
2 1 1
1 1
样例输出
2
3
lct板子题了吧
如果x会跳到y
那就把y设为x的父亲就是了
修改的话维护一个删除和连边就可以了
只需要维护一个每次splay后左子树就是答案了（相当于是一个点的dep）
有个槽点
如果某个点会跳出去，那不能只单纯的直接把父亲设为0，要单独连出一个点，或者打个标记之类的
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
int res=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
int n,m,k[200005],q[200005],ql,rt,fa[200005],lc[200005],rc[200005],siz[200005];
inline bool whic(int x)
{
return rc[fa[x]]==x;
}
inline bool isroot(int x)
{
if(!fa[x]) return true;
return (lc[fa[x]]!=x&&rc[fa[x]]!=x);
}
inline void pushup(int x)
{
siz[x]=siz[lc[x]]+siz[rc[x]]+1;
}
void rotate(int x){
int y=fa[x],z=fa[y],l,r;
if(lc[y]==x)l=0;else l=1;r=l^1;
if(!isroot(y)){if(lc[z]==y)lc[z]=x;else rc[z]=x;}
if(lc[y]==x)
{
fa[x]=z;fa[y]=x;fa[rc[x]]=y;
lc[y]=rc[x];rc[x]=y;
}
else
{
fa[x]=z;fa[y]=x;fa[lc[x]]=y;
rc[y]=lc[x];lc[x]=y;
}
pushup(y);pushup(x);
}
void splay(int u){
if(!u)return;
while(!isroot(u)){
int f=fa[u];
if(!isroot(f)){
if(whic(u)==whic(f))rotate(f);
else rotate(u);
}
rotate(u);
}
}
void access(int u){
for(int x=0;u;u=fa[x=u]){
splay(u);rc[u]=x;
pushup(u);
}
}
inline void cut(int x)
{
access(x);
splay(x);
fa[lc[x]]=0,lc[x]=0;
pushup(x);
}
inline void link(int x,int y)
{
access(x),splay(x),fa[x]=y;
}
int main(){
n=read();
rt=n+1;
for(int i=1;i<=n;i++){
scanf("%d",k+i);
if(i+k[i]<=n)fa[i]=i+k[i];
else fa[i]=rt;
}
m=read();
int x,y;
for(int i=1;i<=m;i++)
{
int op=read();
if(op==1)
{
x=read();
++x;
access(x),splay(x);
cout<<siz[lc[x]]<<'
';
}
else
{
x=read(),y=read();
++x;
cut(x);
x+y<=n?link(x,x+y):link(x,rt);
}
}
}