记录编号	599391	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	1.949 s
提交时间	2025-03-10 20:47:37	内存使用	5.67 MiB

#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;

const int MAXN = 2e5 + 10;
const int LEN = 450;

int n, m;
int a[MAXN], R[MAXN], L[MAXN], nxt[MAXN], tms[MAXN];

int solve(int x) {
    return (x - 1) / LEN + 1;
}

void rebuild(int x) {
    for (int i = R[x]; i >= L[x]; --i) {
        if (i + a[i] > R[x]) {
            nxt[i] = i + a[i];
            tms[i] = 1;
        } else {
            nxt[i] = nxt[i + a[i]];
            tms[i] = tms[i + a[i]] + 1;
        }
    }
}

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]);
    } 
    
    for (int i = 1; i <= solve(n); ++i) {
        L[i] = (i - 1) * LEN + 1;
        R[i] = min(n, i * LEN);
    }
    for (int i = 1; i <= solve(n); ++i) {
        rebuild(i);
    }
    
    scanf("%d", &m);
    while (m--) {
        int i, j, k;
        scanf("%d %d", &i, &j);
        j++;
        if (i == 1) {
            int ans = 0;
            while (j <= n) {
                ans += tms[j];
                j = nxt[j];
            }
            printf("%d\n", ans);
        } else {
            scanf("%d", &k);
            a[j] = k;
            rebuild(solve(j));
        }
    } 
    return 0;
}