[luogu3203 HNOI2010] 弹飞绵羊 (分块)

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。

Output

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

Sample Input

4

1 2 1 1

3

1 1

2 1 1

1 1

Sample Output

2

3

Solution

比较简单的分块

对每个分块维护两个值：跳出这个块需要的次数、跳出这个块后所在位置

那么查询和修改就很简单了~

Code

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

#define R(i,a,b) for(register int i=(b);i>=(a);i--)

using namespace std;

int rd() {

	int x=0,f=1; char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=200010;

int n,q,blo;

int da[N],cnt[N],to[N],bl[N],l[N],r[N];

void init() {

	R(i,1,n) {

		if(bl[i]!=bl[i+1]) r[bl[i]]=i;

		if(bl[i]!=bl[i-1]) l[bl[i]]=i;

		if(i+da[i]>n) cnt[i]=1,to[i]=n+1;

		else if(i+da[i]>r[bl[i]]) cnt[i]=1,to[i]=i+da[i];

		else cnt[i]=cnt[i+da[i]]+1,to[i]=to[i+da[i]];

	}

}

void query(int x) {

	int ans=0;

	while(x!=n+1) ans+=cnt[x],x=to[x];

	printf("%d\n",ans);

	return ;

}

void change() {

	int x=rd()+1,k=rd();

	da[x]=k;

	R(i,l[bl[x]],x) //1

		if(i+da[i]>n) cnt[i]=1,to[i]=n+1;

		else if(i+da[i]>r[bl[i]]) cnt[i]=1,to[i]=i+da[i];

		else cnt[i]=cnt[i+da[i]]+1,to[i]=to[i+da[i]];

}

int main() {

	n=rd(); blo=sqrt(n);

	F(i,1,n) da[i]=rd(),bl[i]=(i-1)/blo+1;

	init();

	q=rd();

	while(q--) {

		int opt=rd();

		if(opt==1) query(rd()+1);

		else change();

	}

	return 0;

}

巴特西