莫队

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010000;
int n, m;
int num[maxn];
namespace moQueue{
    const int maxnb = sqrt(maxn) + 1;
    struct Query{
        int l;
        int r;
        int id;
        Query(int _l = 0, int _r = 0, int _id = 0){
            l = _l;
            r = _r;
            id = _id;
        }
    };

    int cnt[maxn], belong[maxn];
    int size, bnum;//一个块大小和块的数量 
    int now, ans[maxn];
    Query q[maxn];
    int cmp(Query a, Query b) {
        return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
    }
    void add(int pos) {
        if(!cnt[num[pos]]) ++now;
        ++cnt[num[pos]];
    }
    void del(int pos) {
        --cnt[num[pos]];
        if(!cnt[num[pos]]) --now;
    }
    void init(){
        size = sqrt(n);
        bnum = ceil((double)n / size);
        for(int i = 1; i <= bnum; ++i){
            for(int j = (i - 1) * size + 1; j <= i * size; ++j) {
                belong[j] = i;
            }
        } 
    }
} 

int main() {
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i) scanf("%d", &num[i]);
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &moQueue::q[i].l, &moQueue::q[i].r);
        moQueue::q[i].id = i;
    }
    sort(moQueue::q + 1, moQueue::q + m + 1, moQueue::cmp);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i) {
        int ql = moQueue::q[i].l, qr = moQueue::q[i].r;
        while(l < ql) moQueue::del(l++);
        while(l > ql) moQueue::add(--l);
        while(r < qr) moQueue::add(++r);
        while(r > qr) moQueue::del(r--);
        moQueue::ans[moQueue::q[i].id] = moQueue::now;
    }
    for(int i = 1; i <= m; ++i) printf("%d ", moQueue::ans[i]);
    return 0;
}