题目：
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
Sample Output
题解：
算法1：引用洛谷官网题解：
LCT裸题。
首先，建立一个虚拟节点n+1n+1，绵羊到达这个节点即被弹飞。
对于每个装置，
如果i+Ki<=ni+Ki<=n，则执行Link(i,i+Ki)Link(i,i+Ki)，否则Link(i,n+1)Link(i,n+1)。
对于修改操作，先执行Cut(j,j+Kj)Cut(j,j+Kj)（如果j+Kj>nj+Kj>n则为n+1n+1），再执行Link(j,j+k)Link(j,j+k)（如果j+k>nj+k>n则为n+1n+1），
并把KjKj赋为kk。
对于询问操作，分别执行MakeRoot(y)MakeRoot(y)，Access(n+1)Access(n+1)和Splay(n+1)Splay(n+1)，最终答案即为size[n+1]-1size[n+1]−1。
其中size[i]size[i]表示平衡树中节点ii的子树的大小。
表示第一次做的时候智障了····忘记拿n+1作为整棵树的根节点从而不知道怎么求深度···哎··
另外注意update
算法2：分块算法
这道题用分块算法简单得多···而且时间还要快一点
先分块，用pos[i]维护i会跳到块外的哪一点上，用times[i]维护i跳到块外的对应点上需要多少步，每次询问的时候一边跳pos[i]一边往ans加time[i]就可以了，复杂度为√n
对于修改直接修改这个点到所在块的初始点内的pos和time，复杂度同样为√n；
代码：
1.LCT
#include#include #include #include #include #include #include #include #include using namespace std;const int N=2e5+5;int tag[N],father[N],size[N],son[N][2],stack[N],cnt,to[N];int n,m,a,b,c;inline int R(){ char c;int f=0; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) f=(f<<3)+(f<<1)+c-'0'; return f;}inline void update(int now){ if(now) { size[now]=1; if(son[now][0]) size[now]+=size[son[now][0]]; if(son[now][1]) size[now]+=size[son[now][1]]; }}inline int get(int now){ return son[father[now]][1]==now;}inline void pushdown(int now){ if(tag[now]&&now) { swap(son[now][0],son[now][1]); tag[son[now][0]]^=1; tag[son[now][1]]^=1; tag[now]=0; }}inline bool isroot(int now){ if(!father[now]) return true; else if(son[father[now]][1]!=now&&son[father[now]][0]!=now) return true; else return false;}inline void rotate(int now){ pushdown(father[now]),pushdown(now); int fa=father[now],ofa=father[fa],which=get(now); if(!isroot(fa)&&ofa) son[ofa][son[ofa][1]==fa]=now; son[fa][which]=son[now][which^1],father[son[fa][which]]=fa; son[now][which^1]=fa,father[fa]=now,father[now]=ofa; update(fa),update(now);}inline void splay(int now){ stack[cnt=0]=now; for(int i=now;!isroot(i);i=father[i]) stack[++cnt]=father[i]; for(int i=cnt;i>=0;i--) pushdown(stack[i]); while(!isroot(now)) { if(!isroot(father[now])) rotate(get(father[now])==get(now)?father[now]:now); rotate(now); }}inline void access(int now){ int temp=0; for(;now;temp=now,now=father[now]) { splay(now),son[now][1]=temp; update(now); }}inline void makeroot(int now){ access(now);splay(now);tag[now]^=1;}inline void link(int a,int b){ makeroot(a);father[a]=b;}inline void cut(int a,int b){ makeroot(a);access(b);splay(b); father[a]=son[b][0]=0;}inline int getans(int now){ makeroot(now); access(n+1);splay(n+1); return size[n+1]-1;}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); n=R(); for(int i=1;i<=n+1;i++) size[i]=1; for(int i=1;i<=n;i++) { a=R(); if(a+i<=n&&a!=0) { to[i]=i+a; link(i,a+i); } else if(a+i>n&&a!=0) { to[i]=n+1; link(i,n+1); } } m=R(); while(m--) { a=R(),b=R(); if(a==1) { int ans=getans(b+1); printf("%d\n",ans); } else { c=R();cut(b+1,to[b+1]); if(b+1+c<=n&&c!=0) to[b+1]=b+1+c,link(b+1,b+1+c); else if(b+1+c>n&&c!=0) to[b+1]=n+1,link(b+1,n+1); } } return 0;}
2.分块
#include#include #include #include #include #include #include #include #include using namespace std;const int N=2e5+5;int n,m,times[N],pos[N],a[N],Right[N],Left[N],id[N],s,tots;inline int R(){ char c;int f=0; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) f=(f<<3)+(f<<1)+c-'0'; return f;}int main(){ //freopen("a.in","r",stdin); n=R();s=(int)sqrt(n); for(int i=1;i<=n;i++) { if(i%s==0) id[i]=tots,Right[tots]=i; else if(i%s==1) id[i]=++tots,Left[tots]=i; else id[i]=tots; } for(int i=1;i<=n;i++) a[i]=R(); for(int i=n;i>=1;i--) { int temp=a[i]+i; if(temp>=n+1) pos[i]=-1,times[i]=1; else if(temp<=Right[id[i]]) pos[i]=pos[temp],times[i]=times[temp]+1; else pos[i]=temp,times[i]=1; } m=R();int q,x,y; while(m--) { q=R(); if(q==1) { x=R();int ans=0; for(int i=x+1;i!=-1;i=pos[i]) ans+=times[i]; printf("%d\n",ans); } else { x=R(),y=R(); a[x+1]=y; for(int i=x+1;i>=Left[id[x]];i--) { int temp=i+a[i]; if(temp>=n+1) pos[i]=-1,times[i]=1; else if(temp<=Right[id[i]]) pos[i]=pos[temp],times[i]=times[temp]+1; else pos[i]=temp,times[i]=1; } } } return 0;}