CF1225B2 TV Subscriptions (Hard Version)

本题的简单版和困难版的唯一区别在于数据范围。 BerTV 频道每天会播放 $k$ 部电视剧中的某一部的一个剧集。你已经知道接下来 $n$ 天的播放安排：一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$（$1 \le a_i \le k$），其中 $a_i$ 表示第 $i$ 天将要播放的电视剧编号。 电视剧的订阅是按整部购买的（即包括该剧的所有剧集），每部剧需要单独购买订阅。 你需要购买最少多少部电视剧的订阅，才能保证在某一段连续的 $d$ 天内，所播放的所有剧集都属于你已购买订阅的电视剧？换句话说，你想要购买最少数量的电视剧，使得存在一段长度为 $d$ 的连续天数，这段时间内播放的所有剧集都属于你已购买订阅的电视剧。

第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含三个整数 $n, k, d$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^6$，$1 \le d \le n$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le k$），表示第 $i$ 天播放的电视剧编号。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $t$ 个整数，按输入顺序分别表示每个测试用例的答案。每个答案为你需要购买的最少电视剧订阅数，使得你可以在 BerTV 上连续观看 $d$ 天你已购买订阅的电视剧。注意，你可以连续观看的天数超过 $d$ 也是允许的。

在第一个测试用例中，为了能连续两天观看剧集，你需要购买电视剧 $1$ 和电视剧 $2$ 的订阅。因此答案是 $2$。 在第二个测试用例中，你可以只购买任意一部电视剧的订阅，因为对于每一部剧，都能找到一段连续三天只播放该剧的区间。 在第三个测试用例中，唯一的四天区间内有四部不同的电视剧，因此你需要购买这四部剧的订阅。 在第四个测试用例中，你可以购买电视剧 $3,5,7,8,9$ 的订阅，这样你就可以在最后连续八天观看剧集。 由 ChatGPT 4.1 翻译