[DS记录] P3203 [HNOI2010] 弹飞绵羊

xishanmeigao / 2023-08-23 / 原文

（题目传送门）

虽然是 \(\rm LCT\) 板子，但用来做分块入门

如果没有修改操作，可以 \(O(n)\) 求出每个点的答案

对于每个块里的点，预处理出它跳出这个块的步数，那么查询时就可以 \(O(1)\) 跳过这些块，查询的复杂度 \(O(\sqrt{n})\)

修改一个点时，也就是 \(O(B)\) 暴力修改即可

令 \(B=\sqrt{n}\)，可以达到 \(O(\sqrt{n})\) 的时间复杂度

#include<bits/stdc++.h>
using namespace std;

const int N=200010,BB=5010;

int n,m,e[N];
int B,t,L[BB],R[BB],pos[N],f[N],lk[N];

void prework()
{
	B=sqrt(n);  t=n/B;
	for(int i=1; i<=t; i++)
		L[i]=(i-1)*B+1,R[i]=i*B;
	if(R[t]<n)
		t++,L[t]=R[t-1]+1,R[t]=n;
	for(int i=1; i<=t; i++)
	{
		for(int j=R[i]; j>=L[i]; j--)
		{
			pos[j]=i;
			if(j+e[j]>R[i])
				f[j]=1,lk[j]=j+e[j];
			else
				f[j]=f[j+e[j]]+1,lk[j]=lk[j+e[j]];
		} 
	}
}

void change(int x,int v)
{
	int p=pos[x];  e[x]=v;
	for(int i=R[p]; i>=L[p]; i--)
	{
		if(i+e[i]>R[p])
			f[i]=1,lk[i]=i+e[i];
		else
			f[i]=f[i+e[i]]+1,lk[i]=lk[i+e[i]];
	}
}

int ask(int x)
{
	int p=pos[x],res=f[x];
	for(int i=p+1,cur=lk[x]; i<=t; i++)
	{
		res+=f[cur];
		cur=lk[cur];
	}
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&e[i]);
		
	prework();
	
	scanf("%d",&m);
	while(m--)
	{
		int op,s,k;
		scanf("%d%d",&op,&s);
		
		if(op==1)
			printf("%d\n",ask(++s));
		else
		{
			scanf("%d",&k);
			change(++s,k);
		}
	}

	return 0;
}