LCT裸题，设 $k[i]$ 为位置 $i$ 弹簧的弹力系数，那么从 $i$ 往 $i+k[i]$ 连一条边，显然所有边构成了一个森林
直接 LCT 维护森林，询问 $x$ 就把 $x$ 到根的路径连起来 ($access(x)$) ，然后输出 $x$ 的 $splay$ 的节点数就好了
修改也不用那么麻烦，我们 $sccess(x),splay(x)$ 后 $c[x][0]$ 的子树就是所有 $x$ 的祖先节点，直接断开就好了
注意不要 $query(read(),read())$，$read()$在函数里是反着读入的！
代码比 $LCT$ 模板还简单
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; int n,m; int c[N][2],fa[N],sz[N]; inline void pushup(int x) { sz[x]=sz[c[x][0]]+sz[c[x][1]]+1; } inline bool notroot(int x) { return (c[fa[x]][0]==x)|(c[fa[x]][1]==x); } inline void rotate(int x) { int y=fa[x],z=fa[y],d=(c[y][1]==x); if(notroot(y)) c[z][c[z][1]==y]=x; fa[x]=z; fa[y]=x; fa[c[x][d^1]]=y; c[y][d]=c[x][d^1]; c[x][d^1]=y; pushup(y); pushup(x); } inline void splay(int x) { while(notroot(x)) { int y=fa[x],z=fa[y]; if(notroot(y)) { if(c[y][0]==x ^ c[z][0]==y) rotate(x); else rotate(y); } rotate(x); } } inline void access(int x) { for(int y=0;x;y=x,x=fa[x]) splay(x),c[x][1]=y,pushup(x); } inline int query(int x) { access(x);splay(x); return sz[x]; } inline void change(int x,int y) { access(x); splay(x); c[x][0]=fa[c[x][0]]=0; if(x+y<=n) fa[x]=x+y; pushup(x); } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int a; n=read(); for(int i=1;i<=n;i++)//编号从1开始 { sz[i]=1,a=read(); if(i+a<=n) fa[i]=i+a;//连边 } m=read(); int b,c; while(m--) { a=read(); if(a==1) printf("%d ",query(read()+1));//题目编号从0开始，所以要+1 else { b=read(); c=read(); change(b+1,c); } } return 0; }