【BZOJ2002】弹飞绵羊

Description

Lostmonkey发明了一种超级反弹装置。为了在绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿一条直线摆放 n个反弹装置，并按从前往后的方式将反弹装置依次编号为 0 到 n-1，对 0≤i≤n-1，为第 i 个反弹装置设定了初始弹力系数 ki，当绵羊落到第 i 个反弹装置上时，它将被往后弹出 ki 步，即落到第 i+ki 个反弹装置上，若不存在第i+ki个反弹装置，则绵羊被弹飞。绵羊想知道： 从第i个反弹装置开始， 它被弹出几次 （含被弹飞的那次）后会被弹飞。为使游戏更有趣，Lostmonkey 还可以修改某个反弹装置的弹力系数，但任何时候弹力系数均为正整数。

Solution

这个题目不就是LCT的例题嘛？

然而我这个蒟蒻并不会LCT。

那还有什么方法呢？

分块大法好！分块大法好！分块大法好！

nexti 表示 i 跳到下一个块后的位置，stepi表示 i 跳到nexti所需步数。

询问时就单点修改，重构当前块。

查询时就直接跳就行了。

预处理 O(n) ，询问和查询都是 n−−√ 的。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define N 200001 using namespace std; int a[N]; int be[N]; int nx[N],bs[N]; int main() { freopen("bounce.in","r",stdin); freopen("bounce.out","w",stdout); int n; cin>>n; int sz=(int)sqrt(n); int t=n/sz; if(n%sz) t++; int now=1; fo(i,1,n) { scanf("%d",&a[i]); be[i]=now; if(i%sz==0) now++; } fd(i,n,1) { if(i+a[i]>n) nx[i]=n+1,bs[i]=1; else { if(be[i]==be[i+a[i]]) nx[i]=nx[i+a[i]],bs[i]=bs[i+a[i]]+1; else nx[i]=i+a[i],bs[i]=1; } } int q; cin>>q; while(q--) { int p; scanf("%d",&p); if(p==1) { int x; scanf("%d",&x); x++; int ans=0,pos=x; while(pos<=n) ans+=bs[pos],pos=nx[pos]; printf("%d\n",ans); } else { int x,t; scanf("%d %d",&x,&t); x++; a[x]=t; int pos=x; bs[x]=0; while(be[pos]==be[x]) pos=pos+a[pos],bs[x]++; if(pos>n) pos=n+1; nx[x]=pos; fd(i,x-1,1) { if(be[i]!=be[i+1]) break; if(be[i]==be[i+a[i]]) nx[i]=nx[i+a[i]],bs[i]=bs[i+a[i]]+1; else nx[i]=i+a[i],bs[i]=1; } } } }