Bounce 弹飞绵羊 (HYSBZ - 2002)

题目

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input
第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output
2
3

思路：
这道题就是典型的分块入门题了，通过分块，可以缩短复杂度，我们需要统计的则是不同块之间的数据即可

代码如下:(有注释哦~(oﾟvﾟ)ノ）

#include
#include
#include
#include
#include
using namespace std;
const int mx=2e5+10;
int x[mx],y[mx],b[mx],l[mx],r[mx],s[mx];
int n,m;void init()
{memset(x,0,sizeof(x));memset(y,0,sizeof(b));
}void build()//分块操作 
{int block,num;block=sqrt(n+0.5);//每一块大小 num=n/block;//块的数量 if(n%block) num++;//如果没有恰好整分,就最后加一块 for(int i=1;i<=num;i++){l[i]=(i-1)*block+1;//每一块的起点r[i]=i*block;//每一块的终点}r[num]=n;//无论怎样最后一块的最后位置一定为nfor(int i=1;i<=n;i++)b[i]=(i-1)/block+1;//分块操作for(int i=n;i>=1;i--){if(i+s[i]>r[b[i]])//如果可以跳到下一个块 {x[i]=1;y[i]=i+s[i];}else{x[i]=x[i+s[i]]+1;y[i]=y[i+s[i]];}}
}void update(int k,int m)
{s[k]=m;for(int i=k;i>=r[b[k]-1];i--){if(i+s[i]>r[b[i]])//如果可以跳到下一个块 {x[i]=1;y[i]=i+s[i];}else{x[i]=x[i+s[i]]+1;y[i]=y[i+s[i]];}}
}int query(int k)//查询操作 
{int res=0;while(k<=n){res+=x[k];k=y[k];}return res;
}int main()
{while(~scanf("%d",&n)){init();for(int i=1;i<=n;i++)scanf("%d",&s[i]);build();scanf("%d",&m);while(m--){int a,b,c;scanf("%d",&a);if(a==1){scanf("%d",&b);printf("%d\n",query(b+1));//记得加1，因为输入i从0开始，而分块从1开始}else{scanf("%d%d",&b,&c);update(b+1,c);//同理啦~}}}return 0;
}

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