CSES - Distinct Values Queries

#include <bits/stdc++.h>

using namespace std;

void upd(int i, int n, int v, vector<int>& cnt){
    i++;
    while(i <= n) cnt[i] += v, i += (i&-i);
}

int rtv(int i, vector<int>& cnt){
    i++;
    int s = 0;
    while(i) s += cnt[i], i -= (i&-i);
    return s;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, q, c = 0, a, b, l = 0;
    cin >> n >> q;
    vector<int> x(n), cnt(n+1), p(n, -1), ans(q);
    map<int, int> m;
    for(int &z : x){
        cin >> z;
        if(m.find(z) != m.end()) z = m[z];
        else z = m[z] = c++;
    }
    vector< tuple<int, int, int> > qry(q);
    for(int i = 0; i < q; i++){
        cin >> a >> b;
        qry[i] = {--b, --a, i};
    }
    sort(qry.begin(), qry.end());
    upd(0, n, 1, cnt), p[0] = 0;
    for(auto &t : qry){
        tie(b, a, c) = t;
        while(l < b){
            l++;
            if(p[x[l]] != -1) upd(p[x[l]], n, -1, cnt);
            upd(l, n, 1, cnt), p[x[l]] = l;
        }
        ans[c] = rtv(b, cnt);
        if(a) ans[c] -= rtv(a-1, cnt);
        l = b;
    }
    for(int &z : ans) cout << z << "\n";
}