13547번: 수열과 쿼리 5

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

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[100001], res[100000], rtn, l, r, cnt[1000001], s;
struct st {
    int c, x, y, idx;
}q[100000];
int main() {
    scanf("%d", &n);
    rtn = sqrt(n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &q[i].x, &q[i].y);
        q[i].c = q[i].x / rtn*rtn + q[i].y / rtn;
        q[i].idx = i;
    }
    sort(q, q + m, [](st i, st j) {return i.c < j.c; });
    for (int i = 0; i < m; i++) {
        while (l > q[i].x) s += !cnt[a[--l]], cnt[a[l]]++;
        while (r < q[i].y) s += !cnt[a[++r]], cnt[a[r]]++;
        while (l < q[i].x) cnt[a[l]]--, s -= !cnt[a[l++]];
        while (r > q[i].y) cnt[a[r]]--, s -= !cnt[a[r--]];
        res[q[i].idx] = s;
    }
    for (int i = 0; i < m; i++) printf("%d\n", res[i]);
    return 0;
}