记录编号	600112	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	2.021 s
提交时间	2025-04-15 21:38:57	内存使用	6.27 MiB

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,num=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
const int N=200010;
int n,m,k;
int a[N];
int L[N],R[N],bel[N];
int to[N],b[N];
int op,x,y;
int ans;
int main(){
    freopen("bzoj_2002.in","r",stdin);
    freopen("bzoj_2002.out","w",stdout);
	n=read();
	k=ceil(sqrt(n));
	for(int i=1;i<=(n-1)/k+1;i++) L[i]=(i-1)*k+1,R[i]=min(n,i*k);
	for(int i=1;i<=n;i++) bel[i]=(i-1)/k+1;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=n;i>=1;i--){
		if(i+a[i]>R[bel[i]]) to[i]=i+a[i],b[i]=1;
		else to[i]=to[i+a[i]],b[i]=b[i+a[i]]+1;
	}
	m=read();
	while(m--){
		op=read();
		if(op==1){
			x=read()+1;ans=0;
			while(x<=n) ans+=b[x],x=to[x];
			printf("%d\n",ans);
		}
		else{
			x=read()+1;y=read();
			a[x]=y;
			for(int i=R[bel[x]];i>=L[bel[x]];i--){
				if(i+a[i]>R[bel[i]]) to[i]=i+a[i],b[i]=1;
				else to[i]=to[i+a[i]],b[i]=b[i+a[i]]+1;
			}
		}
	}
	return 0;
}