「HNOI2010」弹飞绵羊

发表于 | 分类于 | | 浏览量： 次

什么？LCT？不存在的。蒟蒻我怎么可能会LCT。

传送门

洛谷传送门(咕咕咕)

爆炸BZOJ传送门

题解

听说这题的标算是LCT？我这么菜！怎么可能会LCT！！！看了一眼数据范围，很亲切啊！二话不说直接上分块！

首先，按照分块的套路，把$n$个弹力装置分成若干个块(块的大小取$\sqrt{n}$即可)。然后需要提前构造好两个数组：

1：$step[]$。$step[i]$表示落到第i个弹力装置上的绵羊还需几次才能跳到下一个块里（或者被弹飞）。

2：$pos[]$。$pos[i]$表示落到第i个弹力装置上的绵羊在被弹出当前块后会被弹到哪一个位置上。

这两个数组可以一开始从后往前在$\Theta(n*\sqrt{n})$的时间复杂度内构造出来。(我才不会告诉你我写这个是为了测试markdown的数学公式)询问的时候借助这两个数组就可以在$\Theta(\sqrt{n})$的时间复杂度内通过模拟计算出答案。

然后让我们再来考虑修改的问题。

自己思考一下，不难发现，修改了一个弹力系数之后，只有该块内的两个数组的值可能发生改变，然后从后往前暴力更新一下即可。

代码

比LCT短了不少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=200005;
int n,m,S,Area[maxn],K[maxn],step[maxn],pos[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void Solve(int s)
{
	int p=s+K[s],ret=1;
	while(Area[p]==Area[s]){p=p+K[p];ret++;}
	step[s]=ret;pos[s]=p;
}
inline void Update(int s)
{
	int p=s+K[s],ret=1;
	while(Area[p]==Area[s]){p=p+K[p];ret++;}
	step[s]=ret;pos[s]=p;
	for(int i=s-1;Area[i]==Area[s];i--)
		if(Area[i+K[i]]==Area[i])
			{step[i]=step[i+K[i]]+1;pos[i]=pos[i+K[i]];}
}
inline void Query(int s)
{
	int p=s,ret=0;
	while(p<=n){ret+=step[p];p=pos[p];}
	printf("%d\n",ret);
}
int main()
{
	n=read();S=sqrt(n)+1e-10;
	for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
	for(int i=1;i<=n;i++) K[i]=read();
	for(int i=n;i>=1;i--) Solve(i);
	m=read();
	while(m--)
	{
		int a=read(),b=read()+1;
		if(a==1) Query(b);
		else{int c=read();K[b]=c;Update(b);}
	}
	return 0;
}