记录编号	599368	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	1.885 s
提交时间	2025-03-08 17:27:26	内存使用	6.14 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int n,m,a[N],id[N],len;
int t[N],to[N];
struct node {
	int l,r;
}s[N];
void update (int l,int r) {
	for (int i=r;i>=l;i--) {
        if (i+a[i]>s[id[i]].r) {
            to[i]=i+a[i];
            t[i]=1;
        }else{
            to[i]=to[i+a[i]];
            t[i]=t[i+a[i]]+1;
        }
    }
}
int query (int x) {
    int ans=0;
    while (x<n) {
        ans+=t[x];
        x=to[x];
    }
    return ans;
}
int main () {
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout); 
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	len=sqrt(n);
	for (int i=0;i<n;i++) {
		cin >> a[i];
		id[i]=i/len;
	}
	for (int i=0;i<=id[n-1];i++) {
		s[i].l=i*len;
        s[i].r=(i+1)*len-1;
	}
	s[id[n-1]].r=n-1;
    update(0,n-1);
    cin >> m;
    while (m--) {
    	int opt,x,y;
    	cin >> opt >> x;
    	if (opt==1) cout << query(x) <<"\n";
		else {
			cin >> y;
            a[x]=y;
            update(s[id[x]].l,s[id[x]].r);
		} 
	}
	return 0;
}