记录编号	145583	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.170 s
提交时间	2015-01-09 21:40:54	内存使用	4.13 MiB

//Asm.Def
#include <iostream>
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
#define in stdin
#define MaxInput 8000000
inline void ReSet(char *ch){fread(ch, 1, MaxInput, in);}
inline char *InitQRead(){
	char *str = (char*)malloc(MaxInput);
	ReSet(str);
	return str;
}
inline char Getchar(){
	static char *str = InitQRead(), *ptr = str;
	//if(ptr - str == MaxInput)ReSet(str), ptr = str;
	return *(ptr++);
}
inline void getd(int &x){
	char ch = Getchar();bool neg = 0;
	while(!isdigit(ch) && ch != '-')ch = Getchar();
	if(ch == '-')neg = 1, ch = Getchar();
	x = ch - '0';
	while(isdigit(ch = Getchar()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*=======================================================*/
const int maxn = 200005;

struct Node{
	int size;
	Node *par, *p, *son[2];
	inline Node *top();
	inline void init();
	inline void rot();
	inline void splay();
	inline void update(){size = 1 + son[0]->size + son[1]->size;}
}nil, node[maxn];

inline void Node::init(){size = 1;p = son[0] = son[1] = &nil;}

inline void Node::rot(){
	register bool lr = (this == p->son[1]), plr = (p == p->p->son[1]);
	Node *s = son[lr ^ 1], *pre = p, *ppre = p->p;
	s->p = pre;pre->son[lr] = s;
	son[lr ^ 1] = pre;pre->p = this;
	p = ppre;ppre->son[plr] = this;
	son[lr ^ 1]->update();
}

inline void Node::splay(){
	while(p != &nil){
		register bool lr = (this == p->son[1]), plr =  (p == p->p->son[1]);
		if(p->p != &nil){
			if(lr != plr)rot();
			else p->rot();
		}
		rot();
	}
	update();
}

inline Node* Node::top(){
	register Node *u = this;
	while(u->son[0] != &nil)u = u->son[0];
	return u;
}

inline void split(Node *o, bool lr){
	o->size -= o->son[lr]->size;
	o->son[lr]->p = &nil;o->son[lr] = &nil;
}

inline void Access(Node *u){
	u->splay();
	register Node *v = u->top();v->splay();
	while(v->par != NULL){
		v->par->splay();
		split(v->par, 1);
		v->p = v->par;v->par->son[1] = v;
		v->par->update();
		v = v->par->top();
		v->splay();
	}
	u->splay();
}

int N;
inline void init(){
	getd(N);
	register int i, j;
	for(i = 0;i < N;++i){
		getd(j);
		node[i].init();
		if(i + j < N)node[i].par = node + i + j;
	}
}

inline void Query(){
	static int x;
	getd(x);
	Access(node + x);
	printf("%d\n", node[x].son[0]->size + 1);
}

inline void Change(){
	static int i, j;
	getd(i), getd(j);
	Access(node + i);
	split(node + i, 0);
	if(i + j < N)node[i].par = node + i + j;
	else node[i].par = NULL;
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	freopen("output.txt", "w", stdout);
	#else
		#ifndef ONLINE_JUDGE
			freopen("bzoj_2002.in", "r", stdin);
			freopen("bzoj_2002.out", "w", stdout);
		#endif
	#endif
	int m, i;
	init();
	getd(m);
	while(m--){
		getd(i);
		if(i == 1)Query();
		else Change();
	}
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}