【Hnoi 2010】Bounce 弹飞绵羊（分块）

这个其实是一个非常简单的 基本的分块算法 的入门题
Bounce 弹飞绵羊

这是一个经典的 简单的 分块入门题
有关与分块的 详细的说明见博客：
分块入门及例题讲解（一）

代码如下

#include
#include
using namespace std;
const int maxx=2e5+10;int n,m,a,b,c,block_len;
struct{int k;int to_next_steps;int next_block_positoin;
}device[maxx];
int block_num[maxx];int main(){scanf("%d",&n);block_len=sqrt(n);for(int i=0;i<n;i++){scanf("%d",&device[i].k);block_num[i]=i/block_len+1;}for(int i=n-1;i>=0;i--){if(block_num[i]!=block_num[i+device[i].k]){//已经到下一个块了device[i].next_block_positoin=i+device[i].k;device[i].to_next_steps=1; }else{//还在这个块里面device[i].next_block_positoin=device[i+device[i].k].next_block_positoin;device[i].to_next_steps=device[i+device[i].k].to_next_steps+1; }}scanf("%d",&m);for(int cas=1;cas<=m;cas++){scanf("%d%d",&a,&b);if(a==1){int ans=0;while(b<n){ans+=device[b].to_next_steps;b=device[b].next_block_positoin;}printf("%d\n",ans);}else{scanf("%d",&c);device[b].k=c;int start=(block_num[b]-1)*block_len;for(int i=b;i>=start;i--){if(block_num[i]!=block_num[i+device[i].k]){//已经到下一个块了device[i].next_block_positoin=i+device[i].k;device[i].to_next_steps=1; }else{//还在这个块里面device[i].next_block_positoin=device[i+device[i].k].next_block_positoin;device[i].to_next_steps=device[i+device[i].k].to_next_steps+1; }}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！