[BZOJ 2002]弹飞绵羊 题解

发表于 | 评论数： | 阅读次数：

题面

Description

某天，$Lostmonkey$发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，$Lostmonkey$在地上沿着一条直线摆上$n$个装置，每个装置设定初始弹力系数$k_i$，当绵羊达到第$i$个装置时，它会往后弹$k_i$步，达到第$i+k_i$个装置，若不存在第$i+k_i$个装置，则绵羊被弹飞。绵羊想知道当它从第$i$个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，$Lostmonkey$可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数$n$，表示地上有$n$个装置，装置的编号从$0$到$n-1$,接下来一行有$n$个正整数，依次为那$n$个装置的初始弹力系数。第三行有一个正整数$m$，接下来$m$行每行至少有两个数$i$、$j$，若$i=1$，你要输出从$j$出发被弹几次后被弹飞，若$i=2$则还会再输入一个正整数$k$，表示第$j$个弹力装置的系数被修改成$k$。对于$20\%$的数据$n,m \leq 10000$，对于$100\%$的数据$n \leq 200000,m \leq 100000$

Output

对于每个$i=1$的情况，你都要输出一个需要的步数，占一行。

Sample Input

1
2
3
4
5
6
4
1 2 1 1
3
1 1
2 1 1
1 1

Sample Output

1
2
2
3

分析

据说是$LCT$裸题，然而本蒟蒻并不会，考虑数据范围，$n \leq 200000$，可以用$O(n \sqrt n)$的分块大法。

分块后怎么做呢？

我们记录每一个点跳出它所在的块所需的弹跳次数和它跳出当前块以后落在哪一块。于是我们发现当我们修改一个点$p$以后，我们只需要修改这个块内在点$p$之前的点（准确的说，是块内中途会跳到$p$的点），因为每个点记录的东西只管它跳出它所在的块的一系列状态，至于它后面的命运是不管的。

初始化的代码如下。

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
inline void init() //所有初始化工作 jumptime[i]表示i点跳出块所需的次数，outplace[i]表示i点跳出块以后的位置
{
	size=sqrt(n); //算块大小
	for (register int i=1;i<=size;++i)
	{
		L[i]=(i-1)*size+1;
		R[i]=i*size;
	} //每一块的左右界
	if (R[size]<n)
	{
		++size;
		L[size]=R[size-1]+1;
		R[size]=n;
	} //可能存在的最后一块
	for (register int i=1;i<=size;++i)
		for (register int j=L[i];j<=R[i];++j)
			belong[j]=i; //每一个点在哪一块
	for (register int i=size;i>=1;i--)
		for (register int j=R[i];j>=L[i];j--)
		{
			if (j+a[j]>R[i])
				jumptime[j]=1,outplace[j]=j+a[j]; //如果跳一次就能跳出去，那么跳出去的次数为1，跳出去的位置就是j+a[j]
			else
				jumptime[j]=jumptime[j+a[j]]+1,outplace[j]=outplace[j+a[j]]; //否则跳出去的次数就是jumptime[j+a[j]]+1,跳出去的位置就是outplace[j+a[j]]
		} //由此可知循环要倒序，因为跳不出去的点的状态是由它跳一次跳到的那个点决定的
	return;
}

修改的代码如下

1
2
3
4
5
6
7
8
9
10
inline void change(int p,int k)
{
	a[p]=k; //修改
	for (register int i=p;i>=L[belong[p]];--i) //对p点及块内前面所有点更改状态（虽说只要更改能跳到p的，但是复杂度没什么区别）
		if (i+a[i]>R[belong[i]])
			jumptime[i]=1,outplace[i]=i+a[i]; //这些和上面都一样，相当于改了以后重新算一次，再给它一次机会看看能不能跳出去
		else
			jumptime[i]=jumptime[i+a[i]]+1,outplace[i]=outplace[i+a[i]];
	return;
}

有了这个想法以后询问就十分显然了

从$p$点开始跳，用$ans$变量记录次数，使$p$不断跳跃跳出它所在的块，同时$ans$加上跳出去需要的步数，直到跳出去。

代码如下

1
2
3
4
5
6
7
8
9
10
inline int query(int p)
{
	register int ans=0;
	while (p<=n)
	{
		ans+=jumptime[p]; //加上跳出块所需的步数
		p=outplace[p]; //跳到下一个位置
	}
	return ans;
}

Code

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 200005
#define MAXS 450
using namespace std;
int n,a[MAXN],size,L[MAXS],R[MAXS],belong[MAXN];
int m,opt,pos,num,jumptime[MAXN],outplace[MAXN];

inline void getnum(int &num)
{
	num=0;
	char c=getchar();
	while (!isdigit(c))
		c=getchar();
	while (isdigit(c))
	{
		num=(num<<3)+(num<<1)+(c&15);
		c=getchar();
	}
	return;
}

inline void init()
{
	size=sqrt(n);
	for (register int i=1;i<=size;++i)
	{
		L[i]=(i-1)*size+1;
		R[i]=i*size;
	}
	if (R[size]<n)
	{
		++size;
		L[size]=R[size-1]+1;
		R[size]=n;
	}
	for (register int i=1;i<=size;++i)
		for (register int j=L[i];j<=R[i];++j)
			belong[j]=i;
	for (register int i=size;i>=1;i--)
		for (register int j=R[i];j>=L[i];j--)
		{
			if (j+a[j]>R[i])
				jumptime[j]=1,outplace[j]=j+a[j];
			else
				jumptime[j]=jumptime[j+a[j]]+1,outplace[j]=outplace[j+a[j]];
		}
	return;
}

inline void change(int p,int k)
{
	a[p]=k;
	for (register int i=p;i>=L[belong[p]];--i)
		if (i+a[i]>R[belong[i]])
			jumptime[i]=1,outplace[i]=i+a[i];
		else
			jumptime[i]=jumptime[i+a[i]]+1,outplace[i]=outplace[i+a[i]];
	return;
}

inline int query(int p)
{
	register int ans=0;
	while (p<=n)
	{
		ans+=jumptime[p];
		p=outplace[p];
	}
	return ans;
}

int main()
{
	getnum(n);
	for (register int i=1;i<=n;++i)
		getnum(a[i]);
	init();
	getnum(m);
	while (m--)
	{
		getnum(opt),getnum(pos);
		if (opt==1)
			printf("%d\n",query(pos+1));
		else
		{
			getnum(num);
			change(pos+1,num);
		}
	}
	return 0;
}

通过截图

速度还行。

-------------本文结束,感谢阅读-------------
0%