← 返回题目列表

Codeforces · 1889/C2

C2. 多蕾米的晒衣计划(硬版)

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

这个问题的两个版本之间的唯一区别是 $$$k$$$ 的约束、时间限制和内存限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

Doremy 生活在一个多雨的国家,由 $$$n$$$ 个城市组成,编号从 $$$1$$$ 到 $$$n$$$。

天气预报预测了未来 $$$m$$$ 天的降雨分布。第$$$i$$$天,$$$[l_i, r_i]$$$区间内的城市将下雨。如果一个城市在接下来的 $$$m$$$ 天内永远不会下雨,则该城市被称为干燥城市。

原来多蕾米拥有一种特殊的力量。她可以选择 $$$k$$$ 天,这些天不会下雨。多雷米想要计算出使用特殊力量后最多能有多少个干旱城市。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$2 \le k \le \min(10, m)$$$) — 城市数量,天数,以及 Doremy 可以阻止的下雨天数。

然后,接下来是 $$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — $$$i$$$ 天的降雨覆盖范围。

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

输出

对于每个测试用例,输出一个整数——干旱城市的最大数量。

示例

输入 #1

6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 4
1 5
6 10
2 2
3 7
5 8
1 4
100 6 5
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 3
9 20
3 3
10 11
11 13
6 18

输出 #1

1
2
6
0
1000
17

注意

在第一个测试用例中,如果 Doremy 阻止

- 下雨$$$1,2$$$,然后城市$$$2$$$将会干燥;
- 下雨$$$2,3$$$,那么没有城市会干燥;
- 下雨$$$1,3$$$,那么没有城市会干燥;

所以最多有 $$$1$$$ 干燥城市。

在第二个测试用例中,如果 Doremy 阻止

- 下雨$$$1,2$$$,然后城市$$$1,2$$$将会干燥;
- 下雨$$$2,3$$$,然后城市$$$4,5$$$将会干燥;
- 下雨$$$1,3$$$,然后城市$$$1,5$$$将会干燥。

所以最多有 $$$2$$$ 干旱城市。

在第三个测试用例中,最好防止下雨$$$1,2,4,5$$$。

在第四个测试用例中,总有那么一天,雨水打湿了所有的城市,无法避免。