记录编号	402168	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	1.254 s
提交时间	2017-05-05 10:50:42	内存使用	4.87 MiB

#include <set>
#include <ctime>
#include <queue>
#include <vector>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf = 0x7f7f7f7f;
#define Rep(i, a, b) for(register int i=(a), _endi_=(b); i<=_endi_; i++)
#define Fnext(i, u, goal) for(register int i=head[(u)]; i!=(goal); i=e[i].next)
#define RG register
namespace IO {
	void qkin(int &res){
		int x, f=1; char ch;
		while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
		while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;
	}
	void read(int &a){ qkin(a); }
	void read(int &a,int &b){ qkin(a), qkin(b); }
	void read(int &a,int &b,int &c){ qkin(a), qkin(b), qkin(c); }
}
using namespace IO;
#define maxn 200010

struct node {
	int size; bool tag;
	node  *ch[2], *p;
	node (): size(1), tag(0){ }
	void ref();
	void retag();
	void update();
}mem[maxn], *ptr = mem, *null;
inline void node::ref(){
	size = ch[0]->size + ch[1]->size + 1;
}
inline void node::retag(){
	if(this == null) return; tag ^= 1;
}
inline void node::update(){
	if(this == null || !tag) return;
	ch[0]->retag(); ch[1]->retag(); retag(); swap(ch[0], ch[1]);
}
int islc(node *x){ return x == x->p->ch[0]; }
int isroot(node *x){ 
	if(x->p == null) return 1;
	if(x->p->ch[0] == x || x->p->ch[1] == x) return 0;
	return 1;
}

void rot(node *x,int d){
	node *y = x->ch[d ^ 1];
	if(!isroot(x)) x->p->ch[islc(x) ^ 1] = y;
	y->p = x->p;
	x->ch[d ^ 1] = y->ch[d];
	if(y->ch[d] != null) y->ch[d]->p = x;
	y->ch[d] = x;
	x->p = y;
	x->ref(); y->ref();
}
void splay(node *x){
	x->update();
	for(node *rt=x->p; !isroot(x); rt=x->p){
		if(!isroot(rt)) rt->p->update();
		rt->update(); x->update();
		if(isroot(rt)) { rot(rt, islc(x)); return; }
		if(islc(x) == islc(rt)) rot(rt->p, islc(x));
		else rot(rt, islc(x));
		rot(x->p, islc(x));
	}
}
void access(node *x){
	node *y = null;
	while(x != null){
		splay(x);
		x->ch[1] = y; x->ref();
		y = x; x = x->p;
	}
}
void makeroot(node *x){
	access(x); splay(x); x->retag();
}
void link(node *x, node *y){
	makeroot(x); x->p = y;
}
void cut(node *x, node *y){
	makeroot(x); access(y); splay(y); 
	y->ch[0] = y->ch[0]->p = null; y->ref();
}

void query(node *x, node *y){
	makeroot(x); access(y); splay(y);
	printf("%d\n", y->size - 1);
}
void newnode(){
	node *y = ptr++; *y = node();
	y->ch[0] = y->ch[1] = y->p = null;
}
int n, m, a[maxn];
int main(){
	freopen("bzoj_2002.in", "r", stdin);
	freopen("bzoj_2002.out", "w", stdout);
	null = ptr++; null->size = 0; null->ch[0] = null->ch[1] = null->p = null;
	read(n); Rep(i, 1, n + 1) newnode();
	Rep(i, 1, n){
		read(a[i]); int en = min(n + 1, i + a[i]);
		link(mem + i, mem + en);
	}
	read(m); int op, x;
	Rep(i, 1, m){
		read(op, x); x++;
		if(op == 1){ query(mem + x, mem + n + 1); }
		else {
			int en = min(n + 1, x + a[x]);
			cut(mem + x, mem + en);
			read(a[x]);
			en = min(n + 1, x + a[x]);
			link(mem + x, mem + en);
		}
	}
	return 0;
}