题解 | Different Integers 莫队

【Different Integers题解】

模板题，扔一个比较简洁的代码。

将指针起始位置定义在L=0,R=n+1，然后随着查询操作(l,r)进行移动，使得L=l,R=r。

需要注意的是查询的边界问题，l和r也包含在被查询的区间中。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, len;
int w[N], ans[N];

int get(int x) { return x / len; }

struct Query {
    int id, l, r;

    bool operator<(const Query a) const {
        int i = get(l), j = get(a.l);  // 块的编号
        if (i != j) return i < j;
        return r < a.r;
    }
} q[N];
int cnt[N];

void add(int x, int& res) {
    if (!cnt[x]) res++;
    cnt[x]++;
}

void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x]) res--;
}

int main() {
    while (cin >> n >> m) {
        memset(cnt, 0, sizeof cnt);
        int res = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &w[i]);

        len = sqrt(n);
        for (int i = 0; i < m; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            q[i] = {i, l, r};
        }

        sort(q, q + m);
        int R = n + 1, L = 0;// 双指针
        for (int k = 0; k < m; k++) {
            int id = q[k].id, l = q[k].l, r = q[k].r;
            while (R < r) del(w[R++], res);
            while (R > r) add(w[--R], res);

            while (L < l) add(w[++L], res);
            while (L > l) del(w[L--], res);
            ans[id] = res;
        }
        for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
    }
    return 0;
}