DQUERY - D-query

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 30003;

struct Node {
    int l, r;
    int sum;
    Node *L, *R;

    Node(int l, int r) {
        this->l = l; this->r = r;
        sum = 0;
        L = R = nullptr;
    }

    Node* update(int i) {
        Node* cur = new Node(l, r);
        if (l == r) {
            cur->sum = sum + 1;
        } else {
            if (i <= (l + r >> 1)) {
                cur->L = L->update(i);
                cur->R = R;
            } else {
                cur->R = R->update(i);
                cur->L = L;
            }
            cur->sum = cur->L->sum + cur->R->sum;
        }
        return cur;
    }

    int getPrefixSum(int i) {
        if (i < l) return 0;
        if (r <= i) return sum;
        return L->getPrefixSum(i) + R->getPrefixSum(i);
    }
};

Node* build(int i, int j) {
    Node* cur = new Node(i, j);
    if (i != j) {
        cur->L = build(i, i + j >> 1);
        cur->R = build((i + j >> 1) + 1, j);
    }
    return cur;
}

void compress(int a[], int n) {
    vector<int> b (a + 1, a + 1 + n);
    sort(begin(b), end(b));
    b.resize(unique(begin(b), end(b)) - begin(b));
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(begin(b), end(b), a[i]) - begin(b) + 1;
}


int a[N];
int last[N];
Node* root[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    compress(a, n);

    for (int i = 1; i <= n; ++i) last[a[i]] = n + 1;
    root[n + 1] = build(1, n + 1);
    for (int i = n; i >= 1; --i) {
        root[i] = root[i + 1]->update(last[a[i]]);
        last[a[i]] = i;
    }

    int q; cin >> q;
    while (q--) {
        int i, j; cin >> i >> j;
        cout << (j - i + 1) - root[i]->getPrefixSum(j) << '\n';
    }
    return 0;
}

Download