记录编号	480361	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	1.521 s
提交时间	2017-12-26 20:32:36	内存使用	4.32 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=200005;
int ch[inf][2],fa[inf],siz[inf];
bool lazy[inf];
int n,m,to[inf];
bool get(int x){
	return ch[fa[x]][1]==x;
}
bool isroot(int x){
	return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;
}
void update(int x){
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
void pushdown(int x){
	if(!lazy[x])return ;
	lazy[x]=0;
	int ls=ch[x][0],rs=ch[x][1];
	lazy[ls]^=1;lazy[rs]^=1;
	swap(ch[ls][0],ch[ls][1]);
	swap(ch[rs][0],ch[rs][1]);
}
void zig(int x){
	int old=fa[x],oldf=fa[old];
	pushdown(old);
	pushdown(x);
	bool p=get(x);
	if(!isroot(old))ch[oldf][get(old)]=x;
	fa[x]=oldf;
	fa[ch[old][p]=ch[x][p^1]]=old;
	fa[ch[x][p^1]=old]=x;
	update(old);
	update(x);
}
void splay(int x){
	for(;!isroot(x);zig(x))
		if(!isroot(fa[x]))zig(get(x)==get(fa[x])?fa[x]:x);
}
void access(int x){
	int last=0;
	while(x){
		splay(x);
		pushdown(x);//如果x是独自一点成splay，那么我写的splay中并不会下传标记，所以这里额外传一下 
		ch[x][1]=last;
		update(x);//一旦ch发生改变就要update 
		last=x;
		x=fa[x];
	}
}
void makeroot(int x){
	access(x);
	splay(x);
	lazy[x]=1;
	swap(ch[x][0],ch[x][1]);
}
void link(int x,int y){
	makeroot(x);
	fa[x]=y;
}
void cut(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
	ch[y][0]=fa[x]=0;//一旦ch发生更改就要update 
	update(y);
}
int main()
{
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&to[i]);
		to[i]=min(to[i]+i,n+1);
		fa[i]=to[i];
	}
	for(int i=1;i<=n+1;i++)siz[i]=1;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int x;
			scanf("%d",&x);
			x++;
			makeroot(n+1);
			access(x);
			splay(x);
			printf("%d\n",siz[x]-1);
		}
		else {
			int x,y;
			scanf("%d%d",&x,&y);
			x++;
			cut(x,to[x]);
			to[x]=min(n+1,y+x);
			link(x,to[x]);
		}
	}
	return 0;
}