洛谷 P3203 [HNOI2010]弹飞绵羊

分块

\(O(n\sqrt{n})\)

也可以LCT，不过此题分块是很精妙的，值得学习

如果直接维护从i出发跳出去需要多少步，修改x时就需要修改x之前的所有点

但如果维护从i出发跳出块需要多少步，则块外的不会跳到x上，不受影响，只用修改块内的点，单次修改复杂度降至\(\sqrt{n}\)

询问时只用跳块，故也是\(\sqrt{n}\)的

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))

const int N=200000+10,inf=0x3f3f3f3f,M=1010;

int n,K[N],L[M],R[M],pos[N],cost[N],nxt[N];

inline void read(int &x){
    x=0;char f=1,c=getchar();
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

int cal(int x){
    int ans=0;
    while(x){
        ans+=cost[x];
        x=nxt[x];
    }
    return ans;
}

int main(){
    //freopen("input.txt","r",stdin);
    read(n);
    go(i,1,n) read(K[i]);
    int t=sqrt(n);
    go(i,1,t){
        L[i]=R[i-1]+1;
        R[i]=i*t;
    }
    if(R[t]<n){
        L[++t]=R[t-1]+1;
        R[t]=n;
    }
    go(i,1,t)
        go(j,L[i],R[i])
            pos[j]=i;
    com(i,n,1){
        if(i+K[i]>n) cost[i]=1;
        else if(pos[i]==pos[i+K[i]]){
            cost[i]=cost[i+K[i]]+1;
            nxt[i]=nxt[i+K[i]];
        }
        else cost[i]=1,nxt[i]=i+K[i];
    }
    int op,x,k;
    int m;read(m);
    go(i,1,m){
        read(op);read(x);++x;
        if(op==1) printf("%d\n",cal(x));
        else{
            read(k);
            K[x]=k;
            com(j,x,L[pos[x]]){
                if(pos[j]==pos[j+K[j]]){
                    cost[j]=cost[j+K[j]]+1;
                    nxt[j]=nxt[j+K[j]];
                }
                else cost[j]=1,nxt[j]=j+K[j];
            }
        }
    }
    return 0;
}