【[HNOI2010]弹飞绵羊】

发现好像写了一个洛谷上最快的分块

这道题曾经一度感觉非常不可做，因为\(LCT\)的标签以及没有什么思路的分块

但是自从\(yy\)出来一个错误的哈希冲突分块之后（修改的时候挂掉了），就发现这道题不就是我曾经的那个错误的思路吗

这种要往后不断的跳的题目，我们暴力往后跳的话肯定是会爆炸的，因为这样的复杂度完全取决于询问

于是我们就分块好了，一次跳一个不行，那么我们就一次跳一个块好了

我们设\(b[i]\)表示从\(i\)这个位置开始跳，直到跳出所在块的跳跃次数是多少，\(c[i]\)表示\(i\)这个位置跳出所在块之后在哪一个位置

这个样子的话我们就能做到一次跳一个块了，于是现在询问的复杂度有了保证\

这两个数组显然可以预处理出来，因为\(i\)往后跳一部肯定到达了\(i+a[i]\)这个位置，于是就有\(b[i]=b[i+a[i]]+1\)，\(c[i]=c[i+a[i]]\)，对于每一个块倒着预处理就好了

之后就是修改，因为这里只有单点修改，于是我们直接拎出那个块来，修改一下，像预处理那样暴力重构整个块就好了

复杂度也是\(O(\sqrt{n})\)

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define re register

#define maxn 200005

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

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

	return x;

}

int a[maxn];

int b[maxn],c[maxn];

int l[maxn],r[maxn];

int len,Q,n,tot;

inline void Build_Block()

{

	len=std::sqrt(n);

	int k=1;

	while(k<=n)

	{

		l[++tot]=k;

		r[tot]=min(n,l[tot]+len-1);

		k=r[tot]+1;

		for(re int i=r[tot];i>=l[tot];--i)

			if(i+a[i]>r[tot]) b[i]=1,c[i]=i+a[i];

				else b[i]=b[i+a[i]]+1,c[i]=c[i+a[i]];

	}

}

inline int find(int x)

{

	if(x%len==0) return x/len;

	return x/len+1;

}

inline int query(int x)

{

	int ans=0;

	while(x<=n)

	{

		ans+=b[x];

		x=c[x];

	}

	return ans;

}

inline void change(int x,int val)

{

	int t=find(x);

	a[x]=val;

	for(re int i=x;i>=l[t];--i)

		if(i+a[i]>r[t]) b[i]=1,c[i]=i+a[i];

			else b[i]=b[i+a[i]]+1,c[i]=c[i+a[i]];

}

int main()

{

	n=read();

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

		a[i]=read();

	Build_Block();

	Q=read();

	int opt,x,y;

	while(Q--)

	{

		opt=read(),x=read();

		if(opt==1) printf("%d\n",query(x+1));

		else y=read(),change(x+1,y);

	}

	return 0;

}

巴特西

【[HNOI2010]弹飞绵羊】

最新文章

热门文章