CUBE-225: Humanity Has Declined

#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
const int N = 2e5 + 10;
const int K = 2e5 + 10;

int num[K], ar[N], ed[N];
int n, k, q, s = 1, e, cnt;

void Move(){
    while(cnt == k and s <= e){
        ed[s] = e;
        num[ ar[s] ] --;
        if(num[ ar[s] ] == 0 and ar[s] <= k)
            cnt --;
        s ++;
    }
}

int main(){

    scanf("%d%d%d", &n, &k, &q);

    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
        ed[i] = INF;
    }

    for(e=1;e<=n;e++){
        if(num[ ar[e] ] == 0 and ar[e] <= k)
            cnt ++;
        num[ ar[e] ] ++;
        Move();
    }
    Move();

    for(int i=1;i<=q;i++){
        int l, r;
        scanf("%d%d", &l, &r);
        if(ed[l] <= r)
            printf("YES");
        else
            printf("NO");
        printf("\n");
    }

    return 0;
}

/**

num[x] คือ x มีกี่ตัว
ed[i] คือ ตำแหน่งที่น้อยที่สุดหากเริ่มที่ i และมีตัวเลขในช่วง [1, k] ครบ
cnt คือ จำนวนของตัวเลขในช่วง [1, k] ที่แตกต่างกันทั้งหมด

ใช้ two pointer คือ ตำแหน่งเริ่มต้น และตำแหน่งจบ
ว่าหากเริ่มที่ i ควรจบที่ตำแหน่งไหน

*/