欢迎访问~原文出处——
题意概括
沿着一条直线有n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。当它从第i个装置起步时，被弹几次后会被弹飞？此外，还会中途修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
题解
几乎是LCT板子题。
首先根据输入的建树。
然后，如果是询问，那么先把n+1弄成根(rever)，然后从询问的节点a向根打通一条路径(access)，然后把a旋转到树根(splay)，则size[ls[a]]就是答案。
如果是修改，那么就是切掉一条边再连接一条边，这就是LCT(Link_Cut_Tree)的精髓：link和cut。
代码
#include#include #include #include #include using namespace std;const int N=200005;int n,m,Next[N];int fa[N],son[N][2],size[N],rev[N];void pushup(int x){ size[x]=size[son[x][0]]+size[son[x][1]]+1;}bool isroot(int x){ return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}void pushdown(int x){ if (rev[x]){ rev[x]=0; rev[son[x][0]]^=1; rev[son[x][1]]^=1; swap(son[x][0],son[x][1]); }}void pushadd(int x){ if (!isroot(x)) pushadd(fa[x]); pushdown(x);}int wson(int x){ return son[fa[x]][1]==x;}void rotate(int x){ if (isroot(x)) return; int y=fa[x],z=fa[y],L=son[y][1]==x,R=L^1; if (!isroot(y)) son[z][wson(y)]=x; fa[x]=z; fa[y]=x; fa[son[x][R]]=y; son[y][L]=son[x][R]; son[x][R]=y; pushup(y); pushup(x);}void splay(int x){ pushadd(x); for (int y=fa[x];!isroot(x);rotate(x),y=fa[x]) if (!isroot(y)) rotate((wson(x)^wson(y))?x:y);}void access(int x){ int t=0; while (x){ splay(x); son[x][1]=t; t=x; x=fa[x]; }}void rever(int x){ access(x); splay(x); rev[x]^=1;}void link(int x,int y){ rever(x); fa[x]=y;}void cut(int x,int y){ rever(x); access(y); splay(y); fa[x]=son[y][0]=0;}int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&Next[i]); fa[i]=Next[i]=min(i+Next[i],n+1); size[i]=1; } size[n+1]=1; memset(rev,0,sizeof rev); scanf("%d",&m); while (m--){ int op,a,b; scanf("%d",&op); if (op==1){ scanf("%d",&a),a++; rever(n+1); access(a); splay(a); printf("%d\n",size[son[a][0]]); } else { scanf("%d%d",&a,&b),a++; cut(a,Next[a]); link(a,Next[a]=min(a+b,n+1)); } } return 0;}