CF1889C2 Doremy's Drying Plan (Hard Version)

本题的两个版本之间唯一的区别在于 $k$ 的限制、时间限制和内存限制。只有当所有版本的题目都被解决时，你才能进行 Hack。 Doremy 生活在一个多雨的国家，这个国家由 $n$ 个城市组成，城市编号从 $1$ 到 $n$。 天气预报预测了接下来 $m$ 天的降雨分布。在第 $i$ 天，将会在区间 $[l_i, r_i]$ 的城市下雨。如果在接下来的 $m$ 天内某个城市从未下过雨，则称该城市为干燥城市。 Doremy 有一种特殊能力。她可以选择 $k$ 天，在这 $k$ 天里不会下雨。Doremy 想要计算使用这种特殊能力后，最多能有多少个干燥城市。

输入包含多组测试数据。第一行包含一个整数 $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$ 行，每行包含两个整数 $l_i$、$r_i$（$1\le l_i\le r_i\le n$）——表示第 $i$ 天下雨的城市区间。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2\cdot 10^5$。

对于每组测试数据，输出一个整数，表示最多能有多少个干燥城市。

在第一个测试用例中，如果 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$ 天的降雨。 在第四个测试用例中，总有一天的降雨会覆盖所有城市，且无法阻止。 由 ChatGPT 4.1 翻译