【洛谷-P3509】[POI2010]ZAB-Frog

题意#

数轴上有 $n$ 个点，坐标分别为 $p_1, p_2, \cdots, p_n$ 在这些点上按照某些规则跳。

规则是：每次向距当前点第 $k$ 小的点跳，如果有相同距离则向下标较小的跳；

求从每个点出发跳了 $m$ 次后在哪里.

$1\leq k < n\leq 10^6, 1\leq m\leq 10^{18}, 1\leq p_i\leq 10^{18}$.

$\rm{Part}$ $\rm{1}$#

首先，注意到 $k$ 是固定的，所以可以先预处理，对于每个点 $i$，跳一次之后的位置$\operatorname{next}_i$.

这部分使用单调队列处理。

我们知道，对于每个点，距离其前 $k$ 小的点分布在其两侧，可以用一段完整区间覆盖。

所以我们想到，当单调队列枚举到 $i$ 时，单调队列中维护的区间，就是覆盖距离 $i$ 前 $k$ 小的点的区间。这样找到区间内距离最大的点就是我们要求的 $\operatorname{next}_i$，下面考虑考虑如何维护。

对于区间 $[l, r]$ 中的一个点 $i$，距离他最远的点一定是 $l$ 和 $r$ 这两个点中的一个。如果 $r+1$ 到 $i$ 的距离小于了 $l$ 到 $i$ 的距离，说明区间应当向右滑动，如下图，$n=7, k=3$ 的例子：

绿色区间是距离点 $C$ 前 $k$ 小的点，考虑距离点 $D$ 前 $k$ 小的点。

$\rm{Dis(D, F)<Dis(D, A)}$，所以区间要右移一个单位，变成：

又因为 $\rm{Dis(D, E)<Dis(D, B)}$，所以区间要再右移一个单位，变成：

至此，我们能够求出每个点，距离其第 $k$ 小的点的下标。

head = 1, tail = k + 1;
for(int i = 1; i <= n; i++) {
	while(tail + 1 <= n && x[tail + 1] - x[i] < x[i] - x[head]) head++, tail++;
	if(x[tail] - x[i] > x[i] - x[head]) nxt[i] = tail;
	else nxt[i] = head;
}

$\rm{Part}$ $\rm{2}$#

题目要求跳 $m$ 次之后的答案，我们使用类似快速幂的方法，倍增处理即可。

for(int i = 1; i <= n; i++) pos[i] = i;
while(m) {
	if(m & 1) {
		for(int i = 1; i <= n; i++) pos[i] = next[pos[i]];
	}
	m >>= 1;
	for(int i = 1; i <= n; i++) next2[i] = next[i];
	for(int i = 1; i <= n; i++) next[i] = next2[next2[i]];
}

代码#

最终代码在上面两部分的基础上加上 $\rm{I/O}$ 即可。