这个问题的两个版本之间的唯一区别是 $$$k$$$ 的约束、时间限制和内存限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
Doremy 生活在一个多雨的国家,由 $$$n$$$ 个城市组成,编号从 $$$1$$$ 到 $$$n$$$。
天气预报预测了未来 $$$m$$$ 天的降雨分布。第$$$i$$$天,$$$[l_i, r_i]$$$区间内的城市将下雨。如果一个城市在接下来的 $$$m$$$ 天内永远不会下雨,则该城市被称为干燥城市。
原来多蕾米拥有一种特殊的力量。她可以选择 $$$k$$$ 天(在简单版本中,$$$k = 2$$$),在这些天里不会下雨。多雷米想要计算出使用特殊力量后最多能有多少个干旱城市。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$, $$$k = 2$$$) — 城市数量、天数、多蕾米可以阻止的雨。
然后是 $$$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 2 1 5 6 10 2 2 3 7 5 8 1 4 100 6 2 1 100 1 100 1 100 1 100 1 100 1 100 1000 2 2 1 1 1 1 20 5 2 9 20 3 3 10 11 11 13 6 18
输出 #1
1 2 3 0 1000 15
注意
在第一个测试用例中,如果 Doremy 阻止
- 下雨$$$1,2$$$,然后城市$$$2$$$将会干燥;
- 下雨$$$2,3$$$,那么没有城市会干燥;
- 下雨$$$1,3$$$,那么没有城市会干燥;
所以最多有 $$$1$$$ 干燥城市。
在第二个测试用例中,如果 Doremy 阻止
- 下雨$$$1,2$$$,然后城市$$$1,2$$$将会干燥;
- 下雨$$$2,3$$$,然后城市$$$4,5$$$将会干燥;
- 下雨$$$1,3$$$,然后城市$$$1,5$$$将会干燥。
所以最多有 $$$2$$$ 干旱城市。
在第三个测试用例中,最好防止下雨 $$$2,5$$$。
在第四个测试用例中,总是有 $$$4$$$ 天的降雨,湿润了所有城市并且无法阻止。