LCT板子
用一个$p[i]$数组维护每个点指向的下个点。
每次修改时cut*1+link*1就解决了
被弹出界时新设一个点，权为0，作为终点表示出界点。其他点点权为1。
然后统计一下路径就好辣
注意点的编号从0开始
#include<cstdio> inline void Swap(int &a,int &b){a^=b^=a^=b;} #define N 200005 int n,m,ch[N][2],fa[N],s[N],rev[N],p[N]; #define lc ch[x][0] #define rc ch[x][1] inline bool nrt(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;} inline void up(int x){s[x]=s[lc]+s[rc]+1;} inline void Rev(int x){Swap(lc,rc);rev[x]^=1;} inline void down(int x){if(rev[x]) Rev(lc),Rev(rc),rev[x]=0;} void pre(int x){if(nrt(x))pre(fa[x]); down(x);} void turn(int x){ int y=fa[x],z=fa[y],l=(ch[y][1]==x),r=l^1; if(nrt(y)) ch[z][ch[z][1]==y]=x; fa[ch[x][r]]=y ;fa[y]=x; fa[x]=z; ch[y][l]=ch[x][r]; ch[x][r]=y; up(y); up(x); } inline void splay(int x){ pre(x); for(;nrt(x);turn(x)){ int y=fa[x],z=fa[y]; if(nrt(y)) turn(((ch[y][1]==x)^(ch[z][1]==y))?x:y); } } inline void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),rc=y,up(x);} inline void makert(int x){access(x);splay(x);Rev(x);} inline int find(int x){ access(x);splay(x);down(x); while(lc) x=lc,down(x); splay(x); return x; } inline void link(int x,int y){makert(x); if(find(y)!=x)fa[x]=y;} inline void cut(int x,int y){ makert(x); if(find(y)==x&&fa[y]==x&&!ch[y][0]) fa[y]=rc=0,up(x); } inline void split(int x,int y){makert(x);access(y);splay(y);} int main(){ scanf("%d",&n); int q1,q2,q3; for(int i=1;i<=n;++i){ scanf("%d",&p[i]); p[i]=p[i]+i>n ? n+1:p[i]+i; link(i,p[i]); } scanf("%d",&m); while(m--){ scanf("%d%d",&q1,&q2);++q2; if(q1==1) split(n+1,q2),printf("%d ",s[q2]-1); else{ cut(q2,p[q2]); scanf("%d",&q3); p[q2]=q2+q3>n?n+1:q2+q3; link(q2,p[q2]); } }return 0; }