BZOJ 2002：Bounce 弹飞绵羊（分块）

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB

Submit: 14944 Solved: 7598

[Submit][Status][Discuss]

Description

某天，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

思路

将n个弹力系统进行分块，分块的长度为 $BZOJ 2002：Bounce 弹飞绵羊（分块）$ ，一共分成 $BZOJ 2002：Bounce 弹飞绵羊（分块）$ 块，然后在每块中进行操作

在进行更新的时候只需对更新位置所在的分块进行更新就可以了

修改和查询的复杂度都是 $BZOJ 2002：Bounce 弹飞绵羊（分块）$ ，第一次读入完成更新的时候复杂度为 $BZOJ 2002：Bounce 弹飞绵羊（分块）$

AC代码

/*

* @Author: WZY

* @School: HPU

* @Date:   2018-10-13 17:08:28

* @Last Modified by:   WZY

* @Last Modified time: 2018-10-13 17:35:39

*/

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#include <time.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

#define bug cout<<"---------"<<endl

#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"

const double E=exp(1);

const int maxn=1e6+10;

const int mod=1e9+7;

using namespace std;

int n,m,block;

int a[maxn];

int step[maxn];//记录到当前位置跳了多少次

int Next[maxn];//记录下一个位置

inline void update(int i)

{

	// pos记录当前的位置

	int pos=i+a[i];

	// 如果跳了出去

	if(pos>=n)

	{

		step[i]=1;

		Next[i]=-1;

	}

	// 如果跳出当前分块

	else if(pos>=(i/block+1)*block)

	{

		step[i]=1;

		Next[i]=pos;

	}

	// 还在当前分块

	else

	{

		step[i]=step[pos]+1;

		Next[i]=Next[pos];

	}

}

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	#ifndef ONLINE_JUDGE

	    freopen("in.txt", "r", stdin);

	    freopen("out.txt", "w", stdout);

	    double _begin_time = clock();

	#endif

	cin>>n;

	block=sqrt(n);

	for(int i=0;i<n;i++)

		cin>>a[i];

	// 从后往前更新

	for(int i=n-1;~i;i--)

		update(i);

	cin>>m;

	while(m--)

	{

		int x,y,z;

		cin>>x;

		if(x==1)

		{

			int ans=0;

			cin>>y;

			for(int i=y;i!=-1;i=Next[i])

				ans+=step[i];

			cout<<ans<<endl;

		}

		else

		{

			cin>>y>>z;

			// 更新a[y]的值

			a[y]=z;

			// 只更新y所在分块的数据

			for(int i=y;i>=(y/block)*block;i--)

				update(i);

		}

	}

	#ifndef ONLINE_JUDGE

	    double _end_time = clock();

	    printf("time = %lf ms.", _end_time - _begin_time);

	#endif

	return 0;

}

秒客网