自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:31:23，当前版本为作者最后更新于2021-07-13 13:36:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

两个月前的一道洛谷月赛题。

在打那场比赛时，我最后一小时才开到这题，最后没调出来正解，赛后也就懒得管了。

但是今天模拟赛里又有这题，所以我就翻出了两个月前的代码重新调了一下，发现就是一个加号打成减号了......

顺便看了下题解，发现没有和我完全一样的做法，那就写一下吧......

这属于是一道比较简单的套路型数据结构题，我们抛开部分分不谈，直接分析正解。

这里给出的是一种不需要线段树或其他高级数据结构的在线做法，唯一需要的是 ST 表和二分。

对于每一个 $i$，考虑蛇 A 如果要进入 $i$ 的副链并要取得胜利，考虑要满足什么样的条件。

1. 蛇 B 向左不断走到达 $i$ 时，蛇 A 没有完全进入副链。

   否则蛇 B 跟着进来，先死的肯定是 A。

2. 蛇 B 从 $i$ 右边某个副链进去，能走的步数一定小于 A 能走的步数。

注意到第二个条件和两蛇长度都无关，首先分析。

假设当前蛇 B 在 $j$ 处（目前轮到 A 进入副链），如果存在一个 $mid\in (i,j]$ 使得 $x_i\leq (j-mid)+x_{mid}$，那么 A 就会输。

所以 A 要赢就要使得 $x_i>\max((j-mid)+x_{mid})$，右侧值对于 $j$ 有单调性，所以我们可以找到最大的 $j$，使得如果 B 在它右侧，那么 A 都会输。

也就是说，我们可以求出一个 $L_i$ 表示，当且仅当 B 头位于 $(i,L_i]$ 时，A 此时进入 $i$ 的副链才能使得条件 $2$ 满足。

这里的求法是先建立 $x_i-i$ 的 ST 表，然后对于每个 $i$ 二分。

同理我们求出 $R_i$ 表示，当且仅当 A 头位于 $[R_i,i)$ 时，B 此时进入 $i$ 的副链才能使得对于 B 必胜的条件来说条件 $2$ 满足。

接下来考虑条件 $1$ 的限制。

在条件 $1$ 中我们假设 B 一直往左走，也就是说 $t$ 秒后 B 的蛇头位置为 $c'=c-t$，再考虑 A 完全进入 $i$ 的副链的时间为第 $i-a+1$ 回合 A 行动之后，所以我们要求 $c-(i-a)\leq i$，也就是 $i\ge \dfrac{c+a}{2}$。

也就是说，只要我们钦定 A 能进入副链的 $i$ 必须落在 $L_0=\max(\dfrac{c+a}{2},b)$ 的右侧，那么条件 $1$ 自然满足。

而判定胜负的方法是：谁先进入一个进入则必胜的副链，谁就赢，所以对于 A 我们就要求出编号最小的进入则必胜的副链。

我们依然采用二分，可以进入的副链区间为 $[L_0,R_0]$，其中 $L_0$ 式子在上面，$R_0=\dfrac{b+c}{2}$ 是相撞位置。

我们要检验 $[L_0,mid]$ 中是否存在一个进入即必胜的副链，对于其中某个 $i$，考虑条件 $2$，当 A 蛇头到达 $i$ 也就是 $i-b$ 回合后，B 蛇头的位置应该是 $c-(i-b)$，根据之前的检验条件，需要 $L_i\ge c-(i-b)$，也就是 $L_i+i\ge c+b$。

所以我们又可以建立 $L_i+i$ 的 ST 表，然后求最大值来检验。

对于 B 最先见到的必胜副链，类似，只不过建立的是 $R_i+i$ 的最小值 ST 表。

综上，我们只使用 ST 表和二分，就在 $O((n+q)\log n)$ 的复杂度内在线地完成了本题。