← 返回题目列表

Codeforces · 1884/C

C. 中等设计

中文机器翻译题面 查看原题

数组 $$$a_1, a_2, \ldots, a_m$$$ 最初用零填充。您将获得 $$$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$$$ 的所有值后),计算 $$$\max(a)$$$ 作为 $$$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$$$ 行描述了这些段。这些行的第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$)。保证片段是两两不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出给定段集的所有子集之间的最大成本。

示例

输入 #1

6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789

输出 #1

1
3
2
3
4
4

注意

在第一个测试用例中,只有一个段可用。如果我们不选择它,则数组将为 $$$a = [0, 0, 0]$$$,并且此类(空)段子集的成本将为 $$$0$$$。但是,如果我们选择唯一的段,则数组将为 $$$a = [0, 1, 0]$$$,成本将为 $$$1 - 0 = 1$$$。

在第二个测试用例中,我们可以选择所有段:在这种情况下,数组将为 $$$a = [0, 1, 2, 3, 2, 1, 0, 0]$$$。成本将为 $$$3 - 0 = 3$$$。