CF797E Array Queries

这种位置弄来弄去的题一般就分两种，倍增预处理或者根号分治。

现在我们并不关心具体操作，只关心操作次数，所以倍增就不用了。

但暴力预处理仍然行不通，考虑对 \(p\) 进行根号分治：

• \(p>\sqrt n\)，直接暴力，最多操作 \(O(\sqrt n)\) 次。
• \(p<\sqrt n\)，最多有 \(O(\sqrt n)\) 个 \(p\)，预处理它们只需要 \(O(n\sqrt n)\) 的空间和时间。

所以总时间复杂度 \(O((n+q)\sqrt n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define For(i,x,y)for(i=x;i<=(y);i++)
#define Down(i,x,y)for(i=x;i>=(y);i--)
int ans[N][400],a[N];
int read()
{
	int A;
	bool K;
	char C;
	C=A=K=0;
	while(C<'0'||C>'9')K|=C=='-',C=getchar();
	while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
	return(K?-A:A);
}
int main()
{
	int n,q,i,j,thre,p,k,step;
	n=read();
	For(i,1,n)a[i]=read();
	thre=sqrt(n);
	q=read();
	For(i,1,thre)
	Down(j,n,1)ans[j][i]=(j+a[j]+i>n?1:ans[j+a[j]+i][i]+1);
	while(q--)
	{
		p=read(),k=read();
		if(k>thre)
		{
			step=0;
			while(p<=n)step++,p+=a[p]+k;
			printf("%d\n",step);
		}
		else printf("%d\n",ans[p][k]);
	}
	return 0;
}

倍增一类的套路可以戳这里。