记录编号	314315	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	1.997 s
提交时间	2016-10-03 06:42:53	内存使用	3.36 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=200010;
int n,m,block;
int a[maxn],bel[maxn],step[maxn],outgoal[maxn];
void Init(){
	block=(int)sqrt(n+0.0);
	for(int i=1;i<=n;i++) bel[i]=(i-1)/block+1;
	for(int i=n;i>0;i--){
		if(i+a[i]>n) step[i]=1;
		else{
			if(bel[i]==bel[i+a[i]]){
				step[i]=step[i+a[i]]+1;
				outgoal[i]=outgoal[i+a[i]];
			}
			else{
				step[i]=1;
				outgoal[i]=i+a[i];
			}
		}
	}
}
int Qery(int x){
	int ans=0;
	while(x){ ans+=step[x]; x=outgoal[x]; }
	return ans;
}
void Updata(int x){
	for(int i=x;i>(bel[x]-1)*block;i--){
		if(i+a[i]>n){ step[i]=1; outgoal[i]=0; }
		else{
			if(bel[i]==bel[i+a[i]]){
				step[i]=step[i+a[i]]+1;
				outgoal[i]=outgoal[i+a[i]];
			}
			else{
				step[i]=1;
				outgoal[i]=i+a[i];
			}
		}
	}
}
int main(){
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	Init();
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int z;scanf("%d",&z);
		if(z==1){
			int x;scanf("%d",&x); x++;
			printf("%d\n",Qery(x));
		}
		else{
			int x,y;scanf("%d%d",&x,&y); x++;
			a[x]=y; Updata(x);
		}
	}
	//system("pause");
	return 0;
}