设猫猫虫的能力值为 $x$（初始值 $x=0$）。有 $n$ 场比赛，第 $i$ 场比赛的难度是 $a_i$，隐藏分是 $b_i$。当且仅当猫猫虫当前的能力值 $x \leq a_i$ 时，猫猫虫才会参加这场比赛，然后它的能力值将被重置为 $\max(b_i, x)$。

现在您可以任意安排比赛的顺序，请问猫猫虫最多能参加多少场比赛？

$1\le n\le 10^6$。

标签：Ad-hoc。

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

• 上升类：$a_i < b_i$。
• 下降类：$a_i \ge b_i$。

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

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

性质 2
一场上升类 $(a_1,b_1)$ 和一场下降类 $(a_2,b_2)$ 冲突，也即二者只能参加其一的充要条件是 $a_1<b_2\le a_2<b_1$。
其他情况都可以通过一些策略做到能够参加这两场上升类和下降类。

可以通过分类讨论证明。

解法一

于是答案可写成：

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

其中 $I$ 表示决定参加的上升类场次的集合。$c_i$ 为被 $(a_i, b_i)$ 严格包含的下降类个数。等价于在上升类上做带权区间调度：每个上升区间的权重 $w_i = 1 - c_i$，求不相交区间的最大权和。

关键在于高效计算每个 $c_i$： 把所有下降类按 $a$ 升序排序，维护一个按 $b$ 的树状数组。按上升类的 $b$ 升序遍历到当前 $b_i$ 时，把所有满足 $a_j < b_i$ 的下降类加入 BIT（在其 $b_j$ 处 $+1$）。此时

$$c_i = \text{已加入个数} - \text{BIT.prefix}(a_i),$$

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

随后在上升类上做标准的带权区间调度 DP： 将上升类按 $b$ 升序排序，预处理每个区间的前驱 $p(i)$（使得 $b_p(i) \leq a_i$ 且 $p(i)$ 最大），转移

$$\text{dp}[i] = \max (\text{dp}[i - 1], \text{dp}[p(i)] + w_i).$$

解法二

当一场上升类和一场下降类冲突时，参加上升类会导致猫猫虫的能力值变得更大，是不优的。因此，应当舍弃所有满足“存在一个下降类 $(a_2,b_2)$，使得 $a_1<b_2\leq a_2<b_1$”的上升类 $(a_1,b_1)$。

关于舍弃，可以把上升类 $(a_1,b_1)$ 看作权值为 $0$ 的区间 $[a_1,b_1]$，把下降类 $(a_2,b_2)$ 看作权值为 $1$ 的区间 $[b_2,a_2]$。将所有区间按照右端点为第一关键字从小到大，权值为第二关键字从小到大排序。排序后扫描所有区间，并维护当前扫描过的权值为 $1$ 的区间的左端点最大值 $l_{max}$。如果扫描到一个权值为 $0$ 的区间的左端点小于 $l_{max}$，那么应当舍弃它对应的上升类。

舍弃完后，显然所有的下降类都是能够参加的。因此可以不管下降类，只用考虑剩下没被舍弃的上升类。剩下没被舍弃的上升类最多能参加多少场，显然可以用动态规划求解。

一个更简单的代码写法

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

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

时间复杂度：$O(n \log n)$，空间复杂度：$O(n)$。