Description
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Input
第一行包含一个整数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
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
这道题有两种做法，一种是分块，另一种是LCT。
分块的思路就是把所有的点分成sqrt(n)块，对于每个点我们都记录两个信息：它走出当前分块所需的步数、它走出当前分块所走到的地方。这两个直接在分块里暴力处理。然后在统计答案时从后往前用一个类似前缀和的思路累加即可。 修改只要暴力修改分块里n及其左边的点即可。
#include<bits/stdc++.h> using namespace std; int i,j,k,n,m,tot,ans,blo; int a[200005]; struct node{ int pl,t; }f[200005]; int read(){ char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0'; while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x; } int main() { n=read();blo=sqrt(n); for(int i=0;i<n;i++) a[i]=read(); for(int i=n-1;i>=0;i--){ int nxt=i+a[i]; if(nxt>n-1||nxt>=(i/blo+1)*blo) f[i].t=1,f[i].pl=nxt; else f[i].t=f[nxt].t+1,f[i].pl=f[nxt].pl; } m=read(); for(int i=1;i<=m;i++){ int rec=read(); if(rec==1){ int x=read();ans=0; for(int j=x;j<=n-1;j=f[j].pl) ans+=f[j].t; printf("%d\n",ans); } else{ int p=read(),x=read(); a[p]=x; for(int j=p;j>=p/blo*blo;j--){ int nxt=j+a[j]; if(nxt>n-1||nxt>=(j/blo+1)*blo) f[j].t=1,f[j].pl=nxt; else f[j].t=f[nxt].t+1,f[j].pl=f[nxt].pl; } } } return 0; }这题用LCT的思路就会很简单，对于点x，直接link(x,to[x])即可。修改的时候就cut(x,to[x])然后link(x,new)即可。 答案就是x到n+1的路径上的点数，直接统计即可。
#include<bits/stdc++.h> #define MAXN 200005 using namespace std; int read(){ char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-'); if(c=='-') y=-1;else x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x*y; } struct LCT{ int son[MAXN][2],val[MAXN],siz[MAXN],fa[MAXN],rev[MAXN],sta[MAXN]; void up(int k){siz[k]=siz[son[k][0]]+siz[son[k][1]]+val[k];} int isroot(int k){ return son[fa[k]][0]!=k&&son[fa[k]][1]!=k; } void revers(int k){ swap(son[k][0],son[k][1]); rev[k]^=1; } void down(int k){ if(rev[k]){ revers(son[k][0]); revers(son[k][1]); rev[k]=0; } } void rotate(int k){ if(isroot(k)) return; int f=fa[k],gran=fa[f],d=(son[f][1]==k),w=son[k][d^1]; if(!isroot(f)) son[gran][son[gran][1]==f]=k; fa[k]=gran;fa[f]=k;if(w)fa[w]=f; son[k][d^1]=f;son[f][d]=w; up(f);up(k); } void splay(int k){ int y=k,z=0;sta[++z]=y; while(!isroot(y)) sta[++z]=y=fa[y]; while(z) down(sta[z--]); while(!isroot(k)){ y=fa[k];z=fa[y]; if(!isroot(y)) rotate((son[y][1]==k)^(son[z][1]==y)?k:y); rotate(k); } up(k); } void access(int k){ int x=0; do{ splay(k);son[k][1]=x;up(k);x=k;k=fa[k]; }while(k); } void makeroot(int k){ access(k);splay(k);revers(k); } void split(int x,int y){ makeroot(x);access(y);splay(y); } void link(int x,int y){ makeroot(x);fa[x]=y; } void cut(int x,int y){ split(x,y); fa[x]=son[y][0]=0; up(y); } }T; int n,m,go[MAXN]; int main() { n=read(); for(int i=1;i<=n;i++) T.val[i]=1; for(int i=1;i<=n;i++){ go[i]=read(); T.link(i,i+go[i]>n?n+1:i+go[i]); } m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read();y++; if(x==1){ T.split(y,n+1); printf("%d\n",T.siz[n+1]); } else{ int z=read(); T.cut(y,y+go[y]>n?n+1:y+go[y]); T.link(y,y+z>n?n+1:y+z); go[y]=z; } } return 0; }