lp3203 HNOI2010 弹飞绵羊

依照题意，我们发现，题目求的就是指定点到根的路径长度。
于是，我们对于每一个修改弹力的操作，都可以转化为断边和连边的操作。
那么，我们用Splay维护大小，就可以实现了。
注意：sz数组需要初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=200005;
int fa[N],ch[N][2],sz[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X;
	while(ntrt(X)){
		Y=fa[X];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	} 
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
//令X在Y的上方。 
//由于这里保证存在有边，所以直接断边即可。 
inline void cut(int X){
	access(X),splay(X);
//	splay(Y);
//	fa[X]=ch[Y][0]=0;
	ch[X][0]=fa[ch[X][0]]=0;
}
inline void link(int X,int Y){
	fa[Y]=X;
	updt(X);
}
int a[N];
int n,q;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		sz[i]=1;
//		记得初始化sz数组 
		scanf("%d",&a[i]);
		if(i+a[i]<=n){
			link(i+a[i],i);
		}
	}
	scanf("%d",&q);
	int X,Y,op;
	for(int i=1;i<=q;++i){
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&X);++X;
			access(X),splay(X);
			printf("%d\n",sz[X]);
		}else{
			scanf("%d%d",&X,&Y);++X;
			if(X+a[X]<=n){
				cut(X);
			}
			access(X),splay(X);
			if(X+Y<=n){
				link(X+Y,X);
			}
			a[X]=Y;
		}
	}
}
int main(){
//	freopen("3203.in","r",stdin);
//	freopen("3203.myout","w",stdout);
	init();
	return 0;
}