题解：P14593 [LNCPC 2025] 猫猫虫打 CF

· · 题解

这是本题的官方题解。

把比赛 (a_i,b_i) 分成两类：

:::info[性质 1]{open}

如果所有的比赛都是下降类，那么显然所有的比赛都能够参加。

:::

下面考虑同时有上升类和下降类的情况。

:::info[性质 2]{open}

一场上升类 (a_1,b_1) 和一场下降类 (a_2,b_2) 冲突，也即二者只能参加其一的充要条件是 a_1<b_2\le a_2<b_1。

其他情况都可以通过一些策略做到能够参加这两场上升类和下降类。

:::

可以通过分类讨论证明。

下面介绍两种解法和一种在这些解法的基础上更简单的代码写法，时间复杂度都是 O(n \log n) ，空间复杂度都是 O(n)。

解法一

答案可写成：

\text{ans} = \text{下降类的数量} + \max\limits_{I} \sum\limits_{i \in I} (1 - c_i)

其中 I 是决定参加的上升类场次的集合，c_i 是上升类 (a_i, b_i) 所严格包含的下降类的数量。

求解答案等价于在上升类上做带权区间调度：每个上升类 (a_i,b_i) 对应的上升区间 [a_i,b_i] 的权重 w_i 是 1 - c_i ，求不相交（不含端点）区间的最大权和。

关键在于高效计算每个 c_i ：

  1. 把所有下降类 (a_i,b_i) 按 a_i 升序排序，维护一个按 b_i 的树状数组。
  2. 按上升类的 b_i 升序遍历到当前 b_i 时，把所有满足 a_j < b_i 的下降类 (a_j,b_j) 加入树状数组（在其 b_j 处 +1）。
  3. 此时， c_i = \text{已加入个数} - \text{BIT.prefix}(a_i)

    即" a_j < b_i 并且 b_j > a_i "的个数（严格包含，端点相等不算）。

随后在上升类中做标准的带权区间调度 DP：

  1. 将上升类 (a_i,b_i) 对应的上升区间 [a_i,b_i] 按 b_i 升序排序，预处理每个区间的前驱 p_i （使得 b_{p_i} \leq a_i 并且 p_i 最大）。
  2. 状态转移方程： \text{dp}_i = \max (\text{dp}_{i - 1}, \text{dp}_{p_i} + w_i)

解法二

:::info[性质 3]{open}

当一场上升类和一场下降类冲突时，参加上升类会导致猫猫虫的能力值变得更大，是不优的。

:::

因此，应当舍弃所有满足“存在一个下降类 (a_2,b_2)，使得 a_1<b_2\leq a_2<b_1”的上升类 (a_1,b_1)：

  1. 关于舍弃，可以把上升类 (a_1,b_1) 看作区间 [a_1,b_1]，把下降类 (a_2,b_2) 看作区间 [b_2,a_2]。
  2. 将所有区间按照右端点从小到大排序，当两个区间的右端点相同时，上升类区间排在下降类区间的前面。
  3. 排序后扫描所有区间，并维护当前扫描过的下降类区间的左端点的最大值 l_{max}。
  4. 如果扫描到一个上升类区间的左端点小于 l_{max}，那么应当舍弃它。

舍弃完后，显然所有的下降类都是能够参加的。

因此可以不管下降类，只用考虑剩下没被舍弃的上升类。

剩下没被舍弃的上升类最多能参加多少场，等价于最多不相交（不含端点）区间数量，这是一个经典的贪心区间问题：

  1. 将这些区间按照右端点从小到大排序。
  2. 排序后扫描这些区间：如果当前区间是第一个区间或者和上一个选择的区间不相交，那么选择该区间；否则，跳过该区间。

一种更简单的代码写法

在前面解法的基础上，有一种更简单的代码写法：将所有比赛按照 \max(a_i,b_i) 为第一关键字从小到大，\min(a_i,b_i) 为第二关键字从小到大排序，然后直接模拟猫猫虫打比赛即可。

可以发现这种写法和前面两种解法是等价的。