记录编号	115027	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.683 s
提交时间	2014-08-12 23:44:12	内存使用	4.13 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>

const int MAXN=2e5+10;
const int null=0;

using namespace std;

struct node{
	int fa,left,right;
	int size;
	node(int fa=0,int left=0,int right=0,int size=0):
	fa(fa),left(left),right(left),size(size){}
}nodes[MAXN];

#define fa(x)		nodes[x].fa
#define left(x)		nodes[x].left
#define right(x)	nodes[x].right
#define size(x)		nodes[x].size

//null=ndoes[0]

void update(int u){
	size(u)=1;
	size(u)+=size(left(u))+size(right(u));
}

bool is_root(int x){
	if(fa(x)==null)return true;
	else if(left(fa(x))==x || right(fa(x))==x)return false;
	else return true;
}

void zag(int x){
	int y=fa(x);
	int z=fa(y);
	if(left(z)==y)left(z)=x;else if(right(z)==y)right(z)=x;
	right(y)=left(x) , left(x)=y;
	fa(right(y))=y , fa(x)=z , fa(y)=x;
	update(y);
}

void zig(int x){
	int y=fa(x);
	int z=fa(y);
	if(left(z)==y)left(z)=x;else if(right(z)==y)right(z)=x;
	left(y)=right(x) , right(x)=y;
	fa(left(y))=y , fa(x)=z , fa(y)=x;
	update(y);
}

void print(int u){
	printf("\n\n");
	printf("node:%d info\n",u);
	printf("left:%d right:%d fa:%d\n",left(u),right(u),fa(u));
	printf("size:%d\n",size(u));
	printf("\n\n");
}

void splay(int x){
	int y,z;
	while(is_root(x)==false){
		y=fa(x),z=fa(y);
		if(is_root(y)==true){
			if(left(y)==x)zig(x);else zag(x);
		}else if(left(z)==y){
			if(left(y)==x)zig(y);else zag(x);
			zig(x);
		}else {
			if(right(y)==x)zag(y);else zig(x);
			zag(x);
		}
	}
	update(x);
}

void access(int u){
	int v=null;
	while(u!=null){
		splay(u);
		right(u)=v,update(u);
		v=u , u=fa(u);
	}
}

int cut(int u,int v){
	access(u);
	splay(v),fa(v)=null;
}

int link(int u,int v){
	access(u) , splay(u);
	right(u)=v , fa(v)=u;
	update(u);
}

int query(int u){
	access(u) , splay(u);
	return size(u)-1;
}

int N;
int date[MAXN];

void init(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d",&date[i]);
	}
	int root=N+1;
	for(int i=1;i<=N+1;i++){
		size(i)=1;
	}
	for(int i=N;i>=1;i--){
		int next=i+date[i];
		next=min(next,root);
		link(next,i);
	}
}

void test(){
	for(int i=1;i<=N+1;i++){
		print(i);
	}
}

void work(){
	//test();
	int Q;scanf("%d",&Q);
	for(int q=1;q<=Q;q++){
		int op;scanf("%d",&op);
		if(op==1){
			int ob;scanf("%d",&ob);ob++;
			int ans=query(ob);
			printf("%d\n",ans);
		}else{
			int ob,k;scanf("%d %d",&ob,&k);ob++;
			int old_next=min(date[ob]+ob,N+1);
			int next=min(k+ob,N+1);
			cut(old_next,ob);
			link(next,ob);
			date[ob]=k;
		}
	}
}
int main(){
	//freopen("in.in","r",stdin);
freopen("bzoj_2002.in","r",stdin);
freopen("bzoj_2002.out","w",stdout);
	init();
	work();
	return 0;
}