P7596 题解

· · 题解

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

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

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

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

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

这里给出的是一种不需要线段树或其他高级数据结构的在线做法，唯一需要的是 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) 的复杂度内在线地完成了本题。