P3203 [HNOI2010] 弹飞绵羊
大意
在 \(i\) 的地方会向后跳 \(a[i]\) 次，然后带修询问你最少需要跳几次能跳出这个长度为 \(n\) 的地方
思路
首先我们发现每个点的弹出，会影响下一个点 \(i + a[i]\)，也就是说我们如果暴力的考虑的话，就只需修改的时候向后一直跳。
但是这样很劣啊，我们可以考虑用分块处理这个问题，我们可以考虑倒序处理，当后面的点处理过后，你就可以把前面的点从后面转移。
于是我们只需要记录 \(cnt[i]\) 次才能跳出第 \(i\) 块，以及 \(nxt[i]\) 弹出块后落到的第一个位置。
那么我们就可以分块直接处理这个玩意，当一个点被修改的时候，只会影响这个点所在的块，直接重新对这个块建一遍即可。
代码
#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;
}