题目描述
The only difference between easy and hard versions is constraints.
The BerTV channel every day broadcasts one episode of one of the k TV shows. You know the schedule for the next n days: a sequence of integers a1,a2,…,an $(1≤a_i≤k)$, where ai is the show, the episode of which will be shown in i-th day.
The subscription to the show is bought for the entire show (i.e. for all its episodes), for each show the subscription is bought separately.
How many minimum subscriptions do you need to buy in order to have the opportunity to watch episodes of purchased shows d (1≤d≤n) days in a row? In other words, you want to buy the minimum number of TV shows so that there is some segment of d consecutive days in which all episodes belong to the purchased shows.
输入描述
The first line contains an integer t $(1≤t≤10000)$ — the number of test cases in the input. Then t test case descriptions follow.
The first line of each test case contains three integers n,k and d $(1≤n≤2⋅10^5$, $1≤k≤10^6$, $1≤d≤n)$. The second line contains n integers $a_1$,$a_2$,…,$a_n$ $(1≤a_i≤k)$, where ai is the show that is broadcasted on the i-th day.
It is guaranteed that the sum of the values of n for all test cases in the input does not exceed $2⋅10^5$.
输出描述
Print t integers — the answers to the test cases in the input in the order they follow. The answer to a test case is the minimum number of TV shows for which you need to purchase a subscription so that you can watch episodes of the purchased TV shows on BerTV for d consecutive days. Please note that it is permissible that you will be able to watch more than d days in a row.
题意分析
求长度为D的区间内的最小元素种类数
样例输入
4
5 2 2
1 2 1 2 1
9 3 3
3 3 3 2 2 2 1 1 1
4 10 4
10 8 6 4
16 9 8
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
样例输出
2
1
4
5
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const ll mod=1e9+7;
mii p;
int a[maxn];
int main() {
int t,i;
cin>>t;
while(t--) {
p.clear();
int n,k,d,f,ma=1000000;
cin>>n>>k>>d;
int cnt=d;
int sum=n-d+1;
for(i=1; i<=n; i++) {
cin>>a[i];
p[a[i]]++;
if(i>=d) {
int x=p.size();
ma=min(ma,x);
if(p[a[i-d+1]]>1)p[a[i-d+1]]--;
else p.erase(p.find(a[i-d+1]));
}
}
cout<<ma<<endl;
}
}
