LYDSY 1878

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
int a[50001], cnt[1000005], ans[200005];
struct query
{
    int id, l, r, b;
} Q[200005];
inline bool operator<(const query &x, const query &y) { return x.b < y.b || (x.b == y.b && x.r < y.r); }
int main()
{
    int n, m, S;
    scanf("%d", &n), S = int(sqrt(n));
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        query &q = Q[i];
        scanf("%d%d", &q.l, &q.r);
        q.id = i, q.b = Q[i].l / S;
    }
    std::sort(Q, Q + m);
    for (int i = 0, L = 0, R = 0, tot = 0; i < m; i++)
    {
        int l = Q[i].l, r = Q[i].r;
        while (L < l)
            if (!--cnt[a[L++]]) --tot;
        while (L > l)
            if (!cnt[a[--L]]++) ++tot;
        while (R < r)
            if (!cnt[a[++R]]++) ++tot;
        while (R > r)
            if (!--cnt[a[R--]]) --tot;
        ans[Q[i].id] = tot;
    }
    for (int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}