记录编号	115621	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.202 s
提交时间	2014-08-21 20:48:56	内存使用	3.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEN=200010;
int N,M;
int K[SIZEN]={0};
int outtot[SIZEN]={0},outgoal[SIZEN]={0};
int belong[SIZEN]={0};
int BL;
void calc_out(int i){
	if(i+K[i]>=N){
		outtot[i]=1;
		outgoal[i]=-1;
	}
	else if(belong[i+K[i]]!=belong[i]){
		outtot[i]=1;
		outgoal[i]=i+K[i];
	}
	else{
		outtot[i]=outtot[i+K[i]]+1;
		outgoal[i]=outgoal[i+K[i]];
	}
}
int calc(int x){
	int ans=0;
	while(x!=-1){
		ans+=outtot[x];
		x=outgoal[x];
	}
	return ans;
}
void change(int x,int d){//将x的改成d
	K[x]=d;
	for(int i=x;i>=0&&belong[i]==belong[x];i--) calc_out(i);
}
void prepare(void){
	int tot=0,temp=0;
	for(int i=0;i<N;i++){
		if(temp==BL){
			temp=0;
			tot++;
		}
		belong[i]=tot;
		temp++;
	}
	for(int i=N-1;i>=0;i--) calc_out(i);
}
void work(void){
	scanf("%d",&M);
	int cmd;
	int x,d;
	for(int i=1;i<=M;i++){
		scanf("%d",&cmd);
		if(cmd==1){
			scanf("%d",&x);
			printf("%d\n",calc(x));
		}
		else if(cmd==2){
			scanf("%d%d",&x,&d);
			change(x,d);
		}
	}
}
void read(void){
	scanf("%d",&N);
	BL=sqrt(N+0.5);
	for(int i=0;i<N;i++) scanf("%d",&K[i]);
}
int main(){
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}