Solution for DQUERY - SPOJ with Persistent Segment Tree

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 20, BL = 400;
const double EPS = 3e-16;

struct Node {
    long long lv = 0, rv = 0, sum = 0;
}t[N * 22];

long long a[N], root[N], sz = 0, n, q, last[M];

long long build(long long tl, long long tr){
    long long v = ++sz;
    if(tl != tr){
        long long tm = tl + tr >> 1;
        t[v].lv = build(tl, tm);
        t[v].rv = build(tm + 1, tr);
    }
    return v;
}

long long update(long long v, long long tl, long long tr, long long pos, long long val){
    long long nv = ++sz;
    t[nv] = t[v], t[nv].sum += val;
    if(tl == tr) return nv;
    else {
        long long tm = tl + tr >> 1;
        if(pos <= tm) t[nv].lv = update(t[v].lv, tl, tm, pos, val);
        else t[nv].rv = update(t[v].rv, tm + 1, tr, pos, val);
    }
    return nv;
}

long long get(long long v, long long tl, long long tr, long long l, long long r){
    if(tr < l || r < tl) return 0;
    if(l <= tl && tr <= r) return t[v].sum;
    long long tm = tl + tr >> 1;
    return get(t[v].lv, tl, tm, l, r) + get(t[v].rv, tm + 1, tr, l, r);
}

int main(){
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    long long n; cin >> n;

    root[0] = build(1, n);
    for(long long i = 1; i <= n; i++){
        long long x; cin >> x;
        root[i] = root[i - 1];
        if(last[x] > 0) root[i] = update(root[i], 1, n, last[x], -1);
        last[x] = i;
        root[i] = update(root[i], 1, n, i, 1);
    }

    long long q; cin >> q;
    while(q--){
        long long l, r; cin >> l >> r;
        cout << get(root[r], 1, n, l, r) << "\n";
    }

    return 0;
}