BZOJ2002：[HNOI2010]弹飞绵羊

浅谈分块：https://www.cnblogs.com/AKMer/p/10369816.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2002

显然如果没有修改的话，那么这就是一道倒着扫一遍就完事的傻逼题。记录每个点要往后跳多少次即可，\(step_i\)由\(step_{i+k_i}+1\)更新。

如果修改次数够少，我们也能每次花\(O(n)\)的代价去更新修改的位置及其之前的位置的\(step\)。

但是，出题人往往没有想象的那么良心。

所以我们就用分块解决这个问题，对于每个位置我记录\(step_i\)表示从当前位置跳到下一个块要多少步，\(nxt_i\)表示跳了这么多步之后我会到哪个位置。

所以每次我们都只需要花\(O(\sqrt{n})\)的时间去更新与修改位置在同一个块内并且在它前面的位置的\(step\)即可。

对于每次询问，我们也可以在\(O(\sqrt{n})\)的时间内求出最终步数。

时间复杂度：\(O(m\sqrt{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cmath>

#include <cstdio>

using namespace std;

const int maxn=2e5+5;

int n,m,block;

int k[maxn],bel[maxn],step[maxn],nxt[maxn];

int read() {

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

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int main() {

	n=read(),block=sqrt(n);

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

		k[i]=read(),bel[i]=(i-1)/block+1;

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

		if(bel[i]!=bel[i+k[i]])

			step[i]=1,nxt[i]=i+k[i];

		else step[i]=step[i+k[i]]+1,nxt[i]=nxt[i+k[i]];

	m=read();

	while(m--) {

		int opt=read(),pos=read()+1;

		if(opt==1) {

			int res=0;

			while(pos<=n) {

				res+=step[pos];

				pos=nxt[pos];

			}

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

		}

		else {

			k[pos]=read();

			int tmp=bel[pos];

			while(bel[pos]==tmp) {

				if(bel[pos+k[pos]]!=tmp)

					step[pos]=1,nxt[pos]=pos+k[pos];

				else step[pos]=step[pos+k[pos]]+1,nxt[pos]=nxt[pos+k[pos]];

				pos--;

			}

		}

	}

	return 0;

}

巴特西

BZOJ2002：[HNOI2010]弹飞绵羊

最新文章

热门文章