시간 제한: 2초 메모리 제한: 256MB 입력: 표준 입력 출력: 표준 출력

쉬운 버전과 고급 버전의 유일한 차이점은 제약 조건입니다.

BerTV 채널은 매일 k개의 TV 프로그램 중 하나의 에피소드를 방영합니다. 다음 n일간의 방송 스케줄을 알고 있습니다: 정수 시퀀스 a₁, a₂, ..., aₙ (1≤aᵢ≤k), 여기서 aᵢ는 i일째에 방영될 프로그램입니다.

프로그램 구독은 해당 프로그램의 모든 에피소드에 대해 구매하며(즉, 모든 에피소드에 대해), 각 프로그램은 별도로 구매합니다.

구매한 프로그램의 에피소드를 연속 d일(1≤d≤n) 동시청할 수 있도록 하는 데 필요한 최소 구독 수는 몇 개입니까? 다시 말해, 구매한 프로그램에 속한 에피소드로만 구성된 d일 연속 구간이 존재하도록 하는 최소 TV 프로그램 수를 구하는 것입니다.

입력 첫 번째 줄에는 정수 t(1≤t≤10000)가 주어집니다 - 입력 테스트 케이스의 수. 그 다음 t개의 테스트 케이스 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 세 개의 정수 n, k, d(1≤n≤2⋅10⁵, 1≤k≤10⁶, 1≤d≤n)가 포함됩니다. 두 번째 줄에는 n개의 정수 a₁, a₂, ..., aₙ(1≤aᵢ≤k)가 포함되며, 여기서 aᵢ는 i일째에 방영될 프로그램입니다.

입력의 모든 테스트 케이스에 대한 n 값의 합이 2⋅10⁵를 초과하지 않음이 보장됩니다.

출력 t개의 정수를 출력하십시오 - 입력 테스트 케이스의 순서대로 답변을 출력합니다. 테스트 케이스에 대한 답변은 BerTV에서 구매한 TV 프로그램의 최소 수이어야 합니다. 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

해설 첫 번째 테스트 케이스에서 연속 2일간 프로그램을 시청하려면 프로그램 1과 프로그램 2에 대한 구독을 구매해야 합니다. 따라서 답은 2입니다.

두 번째 테스트 케이스에서는 세 개의 연속된 날짜로만 구성된 구간을 찾을 수 있으므로 임의의 프로그램에 구독을 구매할 수 있습니다.

세 번째 테스트 케이스에서 유일한 4일 구간에는 네 개의 서로 다른 프로그램이 있으므로 이 네 프로그램 모두에 대한 구독이 필요합니다.

네 번째 테스트 케이스에서 프로그램 3, 5, 7, 8, 9에 구독을 구매하면 마지막 8일간 프로그램을 시청할 수 있습니다.

해결 방법: 이 문제를 처음 접했을 때, 모의 알고리즘의 분할 통계와 에라토스테네스 체를 생각했습니다. 작성 후 계속 디버깅을 진행하다가 선배님의 코드를 보고 이해하게 되었습니다.

t개의 입력 테스트 케이스가 있습니다. n은 숫자의 개수, k는 n개 숫자 중 최댓값, d는 연속된 숫자들 중 서로 다른 숫자의 개수(중복되지 않은 숫자 개수)를 나타냅니다.

첫 번째 구간에서 조건에 맞는 숫자들을 표현하고, 모든 것을 찾을 때까지 순서대로 아래로 이동시킬 수 있습니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int MAXN = 1e6 + 10;
set<int> uniqueShows;
map<int,int> frequency;
int showSchedule[MAXN];
int testCases, totalDays, showsCount, consecutiveDays;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> testCases;
    while(testCases--){
        frequency.clear();
        uniqueShows.clear();
        cin >> totalDays >> showsCount >> consecutiveDays;
        for(int i = 1; i <= totalDays; i++)
            cin >> showSchedule[i];

        for(int i = 1; i <= consecutiveDays; i++){
            frequency[showSchedule[i]]++;
            uniqueShows.insert(showSchedule[i]);
        }
        //좌우 경계를 찾고, 모든 것을 찾을 때까지 순서대로 아래로 이동
        int left = 1, right = consecutiveDays, result = uniqueShows.size();
        while(right < totalDays){//같으면 성립하지 않음, 안에 right++이 있으므로
            frequency[showSchedule[left]]--;//오른쪽으로 이동
            if(frequency[showSchedule[left]]==0)//없으면 삭제
                uniqueShows.erase(showSchedule[left]);
            left++;
            right++;
            uniqueShows.insert(showSchedule[right]);//오른쪽으로 이동, 삽입
            frequency[showSchedule[right]]++;//이 단계를 처음에 작성하는 것을 잊었습니다.
            if(uniqueShows.size() < result)
                result = uniqueShows.size();
        }
        cout << result << endl;
    }
    return 0;
}