LCT模板题。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 200500 using namespace std; int n,type,x,y,fath[maxn],size[maxn],tree[maxn][3]; int m,rev[maxn]; int next[maxn],stack[maxn],top=0; bool isroot(int x) { return tree[fath[x]][1]!=x&&tree[fath[x]][2]!=x; } void pushdown(int x) { if (rev[x]) { rev[x]=0; int ls=tree[x][1],rs=tree[x][2]; rev[ls]^=1;rev[rs]^=1; swap(tree[x][1],tree[x][2]); } } void pushup(int now) { int ls=tree[now][1],rs=tree[now][2]; size[now]=size[ls]+size[rs]+1; } void rotate(int x) { int y=fath[x],z=fath[y],l,r; if (tree[y][1]==x) l=1;else l=2; r=3-l; if (!isroot(y)) { if (tree[z][1]==y) tree[z][1]=x; else tree[z][2]=x; } fath[x]=z;fath[y]=x;fath[tree[x][r]]=y; tree[y][l]=tree[x][r];tree[x][r]=y; pushup(y);pushup(x); } void splay(int x) { top=0; stack[++top]=x; for (int i=x;!isroot(i);i=fath[i]) stack[++top]=fath[i]; for (int i=top;i>=1;i--) pushdown(stack[i]); while (!isroot(x)) { int y=fath[x],z=fath[y]; if (!isroot(y)) { if ((tree[z][1]==y)^(tree[y][1]==x)) rotate(x); else rotate(y); } rotate(x); } } void access(int x) { int regis=0; while (x) { splay(x); tree[x][2]=regis; regis=x;x=fath[x]; } } void makeroot(int x) { access(x);splay(x); rev[x]^=1; } void cut(int x,int y) { makeroot(x);access(y); splay(y);tree[y][1]=0;fath[x]=0; } void link(int x,int y) { makeroot(x); fath[x]=y; splay(x); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&type); fath[i]=min(n+1,i+type); next[i]=fath[i]; size[i]=1; } size[n+1]=1; scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d",&type); if (type==1) { scanf("%d",&x);x++; makeroot(n+1); access(x);splay(x);printf("%d ",size[tree[x][1]]); } else { scanf("%d%d",&x,&y);x++; cut(next[x],x);link(min(x+y,n+1),x);next[x]=min(x+y,n+1); } } return 0; }