13546번: 수열과 쿼리 4

https://www.acmicpc.net/problem/13546

#include<cstdio>
#include<algorithm>
#include<list>
using namespace std;
const int MX = 1e5;
int n, m, k, rtn, a[MX + 1], res[MX];
struct st {
    int x, y, idx, c;
}q[MX];
int l = 1, r, bk[317], cnt[MX];
list<int> dq[MX + 1];
int len(int h) {
    return dq[h].empty() ? 0 : dq[h].back() - dq[h].front();
}
void insert(int h) {
    cnt[len(a[h])]--;
    bk[len(a[h]) / rtn]--;
    if (dq[a[h]].empty() || dq[a[h]].back() < h) dq[a[h]].push_back(h);
    else dq[a[h]].push_front(h);
    cnt[len(a[h])]++;
    bk[len(a[h]) / rtn]++;
}
void erase(int h) {
    cnt[len(a[h])]--;
    bk[len(a[h]) / rtn]--;
    if (dq[a[h]].back() == h) dq[a[h]].pop_back();
    else dq[a[h]].pop_front();
    cnt[len(a[h])]++;
    bk[len(a[h]) / rtn]++;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    scanf("%d", &m);
    rtn = sqrt(n);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &q[i].x, &q[i].y);
        q[i].idx = i;
        q[i].c = q[i].x / rtn*rtn + q[i].y / rtn;
    }
    sort(q, q + m, [](st i, st j) {return i.c < j.c || i.c == j.c&&i.y<j.y; });
    cnt[0] = bk[0] = k;
    for (int i = 0; i < m; i++) {
        while (q[i].x < l) insert(--l);
        while (q[i].y > r) insert(++r);
        while (q[i].x > l) erase(l++);
        while (q[i].y < r) erase(r--);
        int j, p;
        for (j = (n - 1) / rtn; !bk[j]; j--);
        for (p = min((j + 1)*rtn, n); !cnt[--p];);
        res[q[i].idx] = p;
    }
    for (int i = 0; i < m; i++) printf("%d\n", res[i]);
    return 0;
}