首页 > 代码库 > [BZOJ 2002][Hnoi2010]Bounce 弹飞绵羊（分块）
[BZOJ 2002][Hnoi2010]Bounce 弹飞绵羊（分块）
Description
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Solution
分块大法好…迷之优雅的暴力
维护每个点跳到下一个块的位置和所需要的次数 修改和查询应该都是sqrt(n)吧
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath> #define MAXN 200002using namespace std;int n,m,init,k[MAXN],bump[MAXN],cnt[MAXN];int main(){ scanf("%d",&n); init=(int)sqrt(n+0.1); for(int i=0;i<n;i++) { scanf("%d",&k[i]); bump[i]=i+k[i]; cnt[i]=1; } for(int i=n-1;i>=0;i--) { int t; while(bump[i]<min((i/init+1)*init,n)) { t=bump[i]; bump[i]=bump[t]; cnt[i]+=cnt[t]; } } scanf("%d",&m); for(int i=1;i<=m;i++) { int x,y,ans,t; scanf("%d%d",&x,&y); if(x==1) { ans=0,t=y; while(t<n) { ans+=cnt[t]; t=bump[t]; } printf("%d\n",ans); } else { scanf("%d",&k[y]); int s=y/init*init; for(int j=y;j>=s;j--) { bump[j]=j+k[j]; cnt[j]=1; while(bump[j]<min((j/init+1)*init,n)) { t=bump[j]; bump[j]=bump[t]; cnt[j]+=cnt[t]; } } } } return 0;}
[BZOJ 2002][Hnoi2010]Bounce 弹飞绵羊（分块）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。