Distinct Value Queries - CSES

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

const int N = 20 * 200005;

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("output.txt","w",stderr);
    #endif
}


struct Vertex {
    Vertex *l, *r;
    int sum;

    Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }
};

Vertex* build(int a[], int tl, int tr) {
    if (tl == tr)
        return new Vertex(a[tl]);
    int tm = (tl + tr) / 2;
    return new Vertex(build(a, tl, tm), build(a, tm+1, tr));
}

int get_sum(Vertex* v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && tr == r)
        return v->sum;
    int tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, min(r, tm))
         + get_sum(v->r, tm+1, tr, max(l, tm+1), r);
}

Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        return new Vertex(new_val);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos, new_val), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos, new_val));
}

Vertex *seg[N];
Vertex *st = new Vertex(NULL, NULL);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for(int i = 0; i < n; i++) {
        a[i] = lower_bound(b.begin(), b.end(), a[i])-b.begin();
    }
    int sz = n - 1;

    st -> l = st;
    st -> r = st;
    vector<int> prev(n, - 1);
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            seg[0] = update(st, 0, n - 1, i, 1);
            prev[a[i]]= i;
        }
        else {
            if(prev[a[i]] == -1) {
                seg[i] = update(seg[i - 1], 0, n - 1, i, 1);
                prev[a[i]] = i;
            }
            else {
                seg[i] = update(seg[i - 1], 0, n - 1, prev[a[i]], 0);
                seg[i] = update(seg[i], 0, n - 1, i, 1);
                prev[a[i]] = i;
            }
        }
    }

    while(m--) {
        int l, r;
        cin >> l >> r;
        l--;r--;
        cout << get_sum(seg[r],0, n - 1, l, r) << "\n";
    }

}