题面
题解
大力分块，分块大小$\sqrt n$，对于每一个元素记一下跳多少次能跳到下一个块，以及跳到下一个块的哪个位置，修改的时候时候只需要更新元素所在的那一块即可，然后询问也是$\sqrt n$的模拟。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
using std::__gcd;
typedef long long ll;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 2e5 + 10, SN = 450, M = 1e5 + 10;
int n, m, k[N], x, y, siz, out[N], step[N];
int bel[N], l[SN], r[SN];
void doit (int L, int R) {
for(int i = R; i >= L; --i) {
int nxt = i + k[i];
if(nxt > R) step[i] = 1, out[i] = nxt;
else step[i] = step[nxt] + 1, out[i] = out[nxt];
}
}
int main () {
read(n), siz = sqrt(n);
for(int i = 1; i <= n; ++i)
read(k[i]), bel[i] = (i - 1) / siz + 1;
for(int i = 1; i <= bel[n]; ++i) {
l[i] = r[i - 1] + 1, r[i] = min(i * siz, n);
doit(l[i], r[i]);
}
read(m); int opt;
while(m--) {
read(opt), read(x), ++x;
if(opt == 1) {
int ret = 0;
while(x <= n) ret += step[x], x = out[x];
printf("%d\n", ret);
} else read(k[x]), doit(l[bel[x]], r[bel[x]]);
}
return 0;
}