记录编号	610496	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	2.030 s
提交时间	2026-01-03 16:33:30	内存使用	5.74 MiB

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 2 * 1e5 + 5;
int n, m, B, sz = 0;
int a[MAXN], cnt[MAXN], nxt[MAXN];

inline void build(int x){
    int l = x * B + 1;
    int r = min(n, (x + 1) * B);
    for(int i = r; i >= l; i--){
        int nx = i + a[i];
        if(nx > n){
            cnt[i] = 1;
            nxt[i] = -1;
        }
        else if(nx > r){
            cnt[i] = 1;
            nxt[i] = nx;
        }
        else{
            cnt[i] = 1 + cnt[nx];
            nxt[i] = nxt[nx];
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

	cin >> n;

    B = sqrt(n);
    sz = (n - 1) / B + 1;

    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 0; i < sz; i++){
        build(i);
    }

    cin >> m;
    while(m --){
        int op; cin >> op;
        if(op == 1){
            int x; cin >> x;
            x ++;
            int res = 0;
            while(x != -1){
                res += cnt[x];
                x = nxt[x];
            }
            cout << res << '\n';
        }
        else{
            int x, y; cin >> x >> y;
            x ++;
            a[x] = y;
            int p = (x - 1) / B;
            build(p);
        }
    }

    return 0;
}