cnyz's Blog

• https://www.luogu.com.cn/problem/P3203

LCT 是不可能的，这辈子都是不可能的。

考虑暴力怎么做？暴力是不是，直接预处理出每个点跳多少步，然后 $O(1)$ 回答，$O(n)$ 重构。

考虑均衡复杂度，将长为 $n$ 的序列分成 $H(n)$ 块，预处理出每个点跳出块的步数与到的点，如果询问就直接跳，最多跳 $\frac{n}{H(n)}$ 次，修改时块内暴力重构即可。

显然 $H(n)$ 取 $\sqrt{n}$ 最优，时间复杂度 $O(m\sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
int n,a[200010],q;
int bl,zk;
int L[200010],R[200010],pos[200010],to[200010];
int in[200010];
void init() {
	for(int i=1;i<=zk;i++) L[i]=(i-1)*bl+1,R[i]=min(n,i*bl);
	for(int i=1;i<=zk;i++)
		for(int j=R[i];j>=L[i];j--) {
			in[j]=i;
			if(j+a[j]>R[i]) pos[j]=j+a[j],to[j]=1;
			else pos[j]=pos[j+a[j]],to[j]=to[j+a[j]]+1;
		}
}
int query(int x) {
	int ret=0;
	while(x<=n) ret+=to[x],x=pos[x];
	return ret;
}
void rebuild(int x) {
	for(int i=R[x];i>=L[x];i--)
		if(i+a[i]>R[x]) pos[i]=i+a[i],to[i]=1;
		else pos[i]=pos[i+a[i]],to[i]=to[i+a[i]]+1;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	bl=sqrt(n),zk=n/bl+(n%bl!=0);
	init();
	scanf("%d",&q);
	for(int i=1;i<=q;i++) {
		int op,x,y;
		scanf("%d %d",&op,&x);x++;
		if(op==1) printf("%d\n",query(x));
		else scanf("%d",&y),a[x]=y,rebuild(in[x]);
	}
}