洛谷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;
}

洛谷P3203弹飞绵羊

原文：https://www.cnblogs.com/Stephen-F/p/9883805.html