【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。

那还有什么方法呢？

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

$next_i$表示$i$跳到下一个块后的位置，$step_i$表示$i$跳到$next_i$所需步数。

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

查询时就直接跳就行了。

预处理$O(n)$，询问和查询都是$\sqrt 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;}}}
}