CF1884C Medium Design

数组 $a_1, a_2, \ldots, a_m$ 初始全部为 $0$。给定 $n$ 个两两不同的区间 $1 \le l_i \le r_i \le m$。你需要从这些区间中任选一个子集（可以为空集）。接下来，进行如下操作： - 对于每个 $i = 1, 2, \ldots, n$，如果区间 $(l_i, r_i)$ 被选入子集，则对于每个 $l_i \le j \le r_i$，将 $a_j$ 加 $1$（即 $a_j$ 变为 $a_j + 1$）。如果区间 $(l_i, r_i)$ 没有被选中，则数组不变。 - 接着（在处理完所有 $i = 1, 2, \ldots, n$ 后），计算 $a$ 中的最大值 $\max(a)$ 和最小值 $\min(a)$。 - 最后，所选区间子集的代价定义为 $\max(a) - \min(a)$。 请你求出所有区间子集的最大代价。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5$，$1 \le m \le 10^9$），分别表示区间的数量和数组的长度。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$），表示第 $i$ 个区间。保证所有区间两两不同。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出所有区间子集的最大代价。

在第一个测试用例中，只有一个区间可选。如果不选它，数组为 $a = [0, 0, 0]$，此时代价为 $0$。如果选择了唯一的区间，数组为 $a = [0, 1, 0]$，代价为 $1 - 0 = 1$。 在第二个测试用例中，可以选择所有区间，此时数组为 $a = [0, 1, 2, 3, 2, 1, 0, 0]$，代价为 $3 - 0 = 3$。 由 ChatGPT 4.1 翻译