莫队

原理

见《进阶指南》第230页。

已知[l, r]的答案，可以快速地求出[l - 1, r]、[l + 1, r]、[l, r - 1]和[l, r + 1]的答案。

模板题

洛谷-P1972-[SDOI2009]HH的项链

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1000010, T = 1010;
struct node {
    int l, r;
    int idx, res;
};
int n, a[N], m;
node q[N];
int L[T], R[T];
int cnt[N], tot;
int curL, curR;

bool cmp1 (const node& a, const node& b) {
    return a.l < b.l;
}
bool cmp2 (const node& a, const node& b) {
    return a.r < b.r;
}
void initialize () {
    sort(q + 1, q + m + 1, cmp1);
    int t = sqrt(m);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
    }
    if (R[t] < m) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = m;
    }
    for (int i = 1; i <= t; ++ i)
        sort(q + L[i], q + R[i] + 1, cmp2);
}
void add (int idx) {
    ++ cnt[a[idx]];
    if (cnt[a[idx]] == 1) ++ tot;
}
void del (int idx) {
    -- cnt[a[idx]];
    if (cnt[a[idx]] == 0) -- tot;
}
int query (int l, int r) {
    while (curL < l) del(curL ++);
    while (curL > l) add(-- curL);
    while (curR > r) del(curR --);
    while (curR < r) add(++ curR);
    return tot;
}
bool cmp3 (const node& a, const node& b) {
    return a.idx < b.idx;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++ i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].idx = i;
    }

    initialize();
    for (int i = q[1].l; i <= q[1].r; ++ i) add(i);
    q[1].res = query(curL = q[1].l, curR = q[1].r);
    for (int i = 2; i <= m; ++ i)
        q[i].res = query(q[i].l, q[i].r);
    sort(q + 1, q + m + 1, cmp3);
    for (int i = 1; i <= m; ++ i) printf("%d\n", q[i].res);
    return 0;
}