#分塊#洛谷 3203 彈飛綿羊

題目

在地上沿着一條直線擺上 n n n個裝置，每個裝置設定初始彈力系數 k i ki ki，當綿羊達到第 i i i個裝置時，它會往後彈 k i ki ki步，達到第 i + k i i+ki i+ki個裝置，若不存在第 i + k i i+ki i+ki個裝置，則綿羊被彈飛。綿羊想知道當它從第 i i i個裝置起步時，被彈幾次後會被彈飛。(帶修改)

分析

首先正解是LCT（動态樹LINK-CUT-TREE），但是問題是我太菜了，是以要用分塊，設 f [ i ] f[i] f[i]為跳出塊的步數， n x [ i ] nx[i] nx[i]為跳到塊外的點，首先提前處理，對于詢問跳着回答，塊内修改

代碼

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#define rr register
using namespace std;
int n,f[200001],nx[200001],pos[200001],l[200001],a[200001],bk;
inline signed iut(){
    rr int ans=0,f=1; rr char c=getchar();
    while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans*f;
}
inline void print(int ans){
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
inline signed ask(int x){
    rr int ans=0;
    while (x<=n) ans+=f[x],x=nx[x];
    return ans;
}
inline void update(int x,int w){
    for (rr int i=l[pos[x]+1]-1;i>=l[pos[x]];--i)
    if (i+a[i]>=l[pos[i]+1]) f[i]=1,nx[i]=i+a[i];
        else f[i]=f[i+a[i]]+1,nx[i]=nx[i+a[i]];
}
signed main(){
    n=iut(); bk=sqrt(n);
    for (rr int i=1;i<=n;++i) a[i]=iut();
    for (rr int i=1;i<=n/bk;++i) l[i]=(i-1)*bk+1; l[n/bk+1]=n+1;
    for (rr int i=1;i<=n/bk;++i)
    for (rr int j=l[i];j<l[i+1];++j) pos[j]=i;
    for (rr int i=n;i;--i)
    if (i+a[i]>=l[pos[i]+1]) f[i]=1,nx[i]=i+a[i];
        else f[i]=f[i+a[i]]+1,nx[i]=nx[i+a[i]];
    for (rr int m=iut();m;--m){
        rr int q=iut(),x=iut()+1;
        if (q&1) print(ask(x)),putchar(10);
            else update(x,a[x]=iut());
    }
    return 0;
}