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