eg：基础莫队——求区间不同数字的个数

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. using namespace std;
    4. const int N = 5e4+5, M = 2e5+5, S = 1e6+5;
    5. int n, m, len;
    6. //cnt[]表示当前询问区间内不同数的个数
    7. int w[N], cnt[S], ans[M];
    8. struct node {
    9.     int id, l, r;
    10. }q[M];
    11. int get(int x) {
    12.     return x / len;
    13. }
    14. bool cmp(node a, node b) {
    15.     if (get(a.l) == get(b.l)) {
    16.         //奇偶优化 
    17.         if (get(a.l) & 1) {
    18.             return a.r < b.r;
    19.         } else {
    20.             return a.r > b.r;
    21.         }
    22.     }
    23.     return get(a.l) < get(b.l); 
    24. }
    25. void add(int x, int& res) {
    26.     if (!cnt[x])
    27.         res++;
    28.     cnt[x]++;
    29. }
    30. void del(int x, int& res) {
    31.     cnt[x]--;
    32.     if (!cnt[x])
    33.         res--;
    34. }
    35. signed main() {
    36.     cin >> n;
    37.     for (int i = 1; i <= n; i++)
    38.         scanf("%lld", &w[i]);
    39.     cin >> m;
    40.     len = sqrt((double)n*n/m);
    41.     for (int i = 1; i <= m; i++) {
    42.         int l, r;
    43.         scanf("%lld%lld", &l, &r);
    44.         q[i] = {i, l, r};
    45.     }
    46.     sort(q+1, q+m+1, cmp);
    47.     int i = 0, j = 1, res = 0;
    48.     for (int k = 1; k <= m; k++) {
    49.         int id = q[k].id, l = q[k].l, r = q[k].r;
    50.         while (i < r) add(w[++i], res);
    51.         while (i > r) del(w[i--], res);
    52.         while (j < l) del(w[j++], res);
    53.         while (j > l) add(w[--j], res);
    54.         ans[id] = res;
    55.     }
    56.     for (int i = 1; i <= m; i++) 
    57.         cout << ans[i] << "\n";
    58.     return 0;
    59. }

    eg：带修改的莫队——单点修改，查询区间不同颜色数量

    #include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5, S = 1e6+5;
int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];
struct query {
    int id, l, r, t;
}q[N];
struct modify {
    int p, c;
}c[N];
int get(int x) {
    return x/len;
}
bool cmp(query a, query b) {
    int al = get(a.l), ar = get(a.r);
    int bl = get(b.l), br = get(b.r);
    if (al != bl) 
        return al < bl;
    if (ar != br)
        return ar < br;
    return a.t < b.t;
}
void add(int x, int& res) {
    if (!cnt[x])
        res++;
    cnt[x]++;
}
void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x])
        res--;
}
signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &w[i]);
    for (int i = 0; i < m; i++) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q') {
            mq++;
            q[mq] = {mq, a, b, mc};
        } else {
            c[++mc] = {a, b};
        }
    }
    len = cbrt((double)n*mc)+1;
    sort(q+1, q+mq+1, cmp);
    int i = 0, j = 1, t = 0, res = 0;
    for (int k = 1; k <= mq; k++) {
        int id = q[k].id, tm = q[k].t;
        int l = q[k].l, r = q[k].r;
        while (i < r) add(w[++i], res);
        while (i > r) del(w[i--], res);
        while (j < l) del(w[j++], res);
        while (j > l) add(w[--j], res);
        while (t < tm) {
            t++;
            if (c[t].p>=j && c[t].p<=i) {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
        }
        while (t > tm) {
            if (c[t].p>=j && c[t].p<=i) {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
            t--;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= mq; i++)
        cout << ans[i] << "\n";
    return 0;
}