非常神奇的分块大法。
每块分 √N 个元素 ， 预处理出来：对于每个点，记录两个量：一个是它要弹几次才能出它所在的这个块，另外一个是它弹出这个块后到哪个点。
查询操作：一块一块跳过去 单次复杂度 O(√N)
修改操作：只需要把相应的块改一遍就好了 这个也是O(√N)
#include#include #include #include #include using namespace std;const int maxn = 200005;const int maxm = 100005;inline int read(){ char ch = getchar(); int f = 1 , x = 0; while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch =getchar();} while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();} return x * f;}int n,a[maxn],m,flag,x,y,ans;int l[maxn],r[maxn],cnt,belong[maxn],to[maxn],step[maxn];void init(){ int t = sqrt(n); if(n / t) cnt = n / t + 1; else cnt = n / t; for(int i=1;i<=cnt;i++){ l[i] = r[i-1] + 1; r[i] = min(l[i] + t - 1 , n); } int x = 1; for(int j=1;j<=n;j++){ belong[j] = x; if(j == r[x] && x <= cnt) x++; } for(int i=n;i>=1;i--){ to[i] = i + a[i]; if(to[i] > r[belong[i]]) step[i] = 1; else { step[i] = step[to[i]] + 1; to[i] = to[to[i]]; } }}int main(){ n = read(); for(int i=1;i<=n;i++) a[i] = read(); init(); m = read(); while(m--){ ans = 0; flag = read(); if(flag == 1){ x = read(); x++; while(x <= n){ ans += step[x]; x = to[x]; } printf("%d\n",ans); } else { x = read(); y = read(); x++; a[x] = y; for(int i=r[belong[x]];i>=l[belong[x]];i--){ to[i] = i + a[i]; if(to[i] > r[belong[i]]) step[i] = 1; else { step[i] = step[to[i]] + 1; to[i] = to[to[i]]; } } } } return 0;}