Count Different - 4

#include <iostream>
#include <cassert>
#include <vector>
#include <map>

using namespace std;

int n;
int m;

const int MAX = 20 * 500000;

int pos;
int sum[MAX], le[MAX], ri[MAX];

typedef int tree;

void init(tree nt, tree t) {
    nt[sum] = t[sum];
    nt[le] = t[le];
    nt[ri] = t[ri];
}

void update(tree t) {
    t[sum] = t[le][sum] + t[ri][sum];
}

tree add(tree t, int tl, int tr, int p, int d) {
    assert(0 <= tl && tl <= p && p < tr && tr <= n + 1);
    tree nt = pos++;
    init(nt, t);

    if (tr - tl == 1) {
        nt[sum] += d;
        return nt;
    }

    int tc = (tl + tr) / 2;
    if (p < tc)
        nt[le] = add(t[le], tl, tc, p, d);
    else
        nt[ri] = add(t[ri], tc, tr, p, d);

    update(nt);
    return nt;
}

int getsum(tree t, int tl, int tr, int l, int r) {
    assert(0 <= tl && tl <= l && l < r && r <= tr && tr <= n + 1);
    if (t == 0)
        return 0;
    if (tl == l && tr == r)
        return t[sum];
    int ans = 0;
    int tc = (tl + tr) / 2;
    if (l < tc)
        ans += getsum(t[le], tl, tc, l, min(r, tc));
    if (r > tc)
        ans += getsum(t[ri], tc, tr, max(l, tc), r);
    return ans;
}

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

    int q;
    cin >> n >> q;

    vector<int> a(n), ne(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    map<int, int> m;
    for (int i = n - 1; i >= 0; i--) {
        if (m.count(a[i]))
            ne[i] = m[a[i]];
        else
            ne[i] = n;
        m[a[i]] = i;
    }

    pos = 1;
    vector<tree> vt(n + 1, 0);
    vt[n] = pos++;
    for (int i = n - 1; i >= 0; i--)
        vt[i] = add(vt[i + 1], 0, n + 1, ne[i], 1);

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        cout << r - l - getsum(vt[l], 0, n + 1, l, r) << ' ';
    }
}