记录编号	501411	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.938 s
提交时间	2018-07-21 17:12:20	内存使用	3.36 MiB

#include<bits/stdc++.h>
#define isroot(x) ((x)!=(x)->p->ch[0]&&(x)!=(x)->p->ch[1])
#define dir(x) ((x)==(x)->p->ch[1])
using namespace std;
const int maxn=200005;
struct node{
	int size;
	node *ch[2],*p;
	node():size(1){}
	void refresh(){size=ch[0]->size+ch[1]->size+1;}
}null[maxn];
void initalize(node*);
node *access(node*);
void link(node*,node*);
void cut(node*);
void splay(node*);
void rot(node*,int);
int n,m;
int main(){
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	null->size=0;
	scanf("%d",&n);
	for(int i=0;i<=n;i++)initalize(null+i);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if(i+x<=n)link(null+i,null+i+x);
	}
	scanf("%d",&m);
	while(m--){
		int t,x;
		scanf("%d%d",&t,&x);
		x++;
		if(t==1)printf("%d\n",access(null+x)->size);
		else{
			int d;
			scanf("%d",&d);
			cut(null+x);
			if(x+d<=n)link(null+x,null+x+d);
		}
	}
	return 0;
}
void initalize(node *x){x->ch[0]=x->ch[1]=x->p=null;}
node *access(node *x){
	node *y=null;
	while(x!=null){
		splay(x);
		x->ch[1]=y;
		(y=x)->refresh();
		x=x->p;
	}
	return y;
}
void link(node *x,node *y){
	splay(x);
	x->p=y;
}
void cut(node *x){
	access(x);
	splay(x);
	x->ch[0]->p=null;
	x->ch[0]=null;
	x->refresh();
}
void splay(node *x){
	while(!isroot(x)){
		if(isroot(x->p)){
			rot(x->p,dir(x)^1);
			break;
		}
		if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1);
		else rot(x->p,dir(x)^1);
		rot(x->p,dir(x)^1);
	}
}
void rot(node *x,int d){
	node *y=x->ch[d^1];
	y->p=x->p;
	if(!isroot(x))x->p->ch[dir(x)]=y;
	if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x;
	(y->ch[d]=x)->p=y;
	x->refresh();
	y->refresh();
}