洛谷P3203弹飞绵羊

传送门啦

非常神奇的分块大法。

每块分 √N 个元素 ， 预处理出来：对于每个点，记录两个量：一个是它要弹几次才能出它所在的这个块，另外一个是它弹出这个块后到哪个点。

查询操作：一块一块跳过去 单次复杂度 O(√N)

修改操作：只需要把相应的块改一遍就好了 这个也是O(√N)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
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;
}