题目描述
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
输入输出格式
输入格式：
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。
接下来一行有n个正整数，依次为那n个装置的初始弹力系数。
第三行有一个正整数m，
接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。
输出格式：
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
输入输出样例
说明
对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
题解：其实更改k的操作就相当于把原来点与他加原来k的连边换成他加当前k的连边，这显然是一个先cut再link的操作。
然后查询操作相当于把n+1（相当于弹飞出去）换到根，然后split(n+1,q+1)就相当于搞出了一条中序遍历为q+1到n+1的splay，输出它的size就可以了
代码如下：
#include<map> #include<set> #include<queue> #include<cmath> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define N 200010 #define lson ch[x][0] #define rson ch[x][1] using namespace std; int size[N],m,n,w[N],tag[N],f[N],ch[N][2]; int not_root(int now) { int x=f[now]; return lson==now||rson==now; } int push_up(int x) { size[x]=size[lson]+size[rson]+1; } int rev(int x) { swap(lson,rson); tag[x]^=1; } int push_down(int x) { if(tag[x]) { rev(lson); rev(rson); tag[x]^=1; } } int rotate(int x) { int y=f[x],z=f[y],kd=ch[y][1]==x,xs=ch[x][!kd]; if(not_root(y)) ch[z][ch[z][1]==y]=x; ch[x][!kd]=y; ch[y][kd]=xs; if(xs) f[xs]=y; f[y]=x; f[x]=z; push_up(y); } int push_all(int x) { if(not_root(x)) { push_all(f[x]); } push_down(x); } int splay(int x) { int y,z; push_all(x); while(not_root(x)) { int y=f[x],z=f[y]; if(not_root(y)) { (ch[y][0]==x)^(ch[z][0]==y)?rotate(x):rotate(y); } rotate(x); } push_up(x); } int access(int x) { for(int y=0;x;y=x,x=f[x]) { splay(x); rson=y; push_up(x); } } int make_root(int x) { access(x);splay(x); rev(x); } int split(int x,int y) { make_root(x); access(y);splay(y); } int find_root(int x) { access(x);splay(x); while(lson) { push_down(x); x=lson; } return x; } int link(int x,int y) { make_root(x); if(find_root(y)==x) return 0; f[x]=y; return 1; } int cut(int x,int y) { make_root(x); if(find_root(y)!=x||f[x]!=y||rson) return 0; f[x]=ch[y][0]=0; return 1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); if(i+w[i]<=n) link(i,i+w[i]); else link(i,n+1); } scanf("%d",&m); while(m--) { int kd; scanf("%d",&kd); if(kd==1) { int from; scanf("%d",&from); from++; split(n+1,from); printf("%d ",size[from]-1); } if(kd==2) { int now,cost; scanf("%d%d",&now,&cost); now++; if(w[now]+now<=n) cut(now,w[now]+now); else cut(now,n+1); w[now]=cost; if(w[now]+now<=n) link(now,w[now]+now); else link(now,n+1); } } }