记录编号	599311	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	2.519 s
提交时间	2025-03-07 21:55:08	内存使用	9.09 MiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
ll n,m,len,cnt;
ll a[N],id[N],step[N];
ll to[N],l[N],r[N];
void init(){
	len=sqrt(n);
	cnt=n/len;
	if(n%len>0) cnt++;
	for(ll i=1;i<=cnt;i++){
		l[i]=(i-1)*len+1;
		r[i]=min(n,i*len);
	}
	for(ll i=1;i<=n;i++){
		id[i]=(i-1)/len+1;
	}
	for(ll i=n;i>=1;i--){
		ll t=i+a[i];
		if(t>r[id[i]]){
			step[i]=1;
			to[i]=t;
		}
		else{
			step[i]=step[t]+1;
			to[i]=to[t];
		}
	}
	return ;
}
void update(ll p,ll d){
	a[p]=d;
	ll idp=id[p];
	ll le=l[idp],ri=r[idp];
	for(ll i=ri;i>=le;i--){
		ll t=i+a[i];
		if(t>r[id[i]]){
			step[i]=1;
			to[i]=t;
		}
		else{
			step[i]=step[t]+1;
			to[i]=to[t];
		}
	}
	return ;
}
ll ask(ll p){
	ll ans=0;
	while(p<=n){
		ans+=step[p];
		p=to[p];
	}
	return ans;
}
int main(){
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	init();
	scanf("%lld",&m);
	ll opt,a1,a2;
	while(m--){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld",&a1);
			ll ans=ask(a1+1);
			printf("%lld\n",ans);
		}
		else{
			scanf("%lld%lld",&a1,&a2);
			update(a1+1,a2);
		}
	}
	return 0;
}