【題解】CSES 1734 Distinct Values Queries

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n, Q, k, a[200005], cnt[200005], ans, res[200005];
vector <int> v;
vector <pair<int, pair<int, int> > > q;
 
bool cmp(pair<int, pair<int, int> > x, pair<int, pair<int, int> > y){
    if (x.second.first/k != y.second.first/k) return x.second.first/k < y.second.first/k;
    else return x.second.second < y.second.second;
}
int id(int x){
    return lower_bound(v.begin(), v.end(), x)-v.begin();
}
void add(int x){
    if (cnt[x] == 0) ans++;
    cnt[x]++;
}
void remove(int x){
    if (cnt[x] == 1) ans--;
    cnt[x]--;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> Q;
    k = sqrt(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i < n; i++){
        a[i] = id(a[i]);
    }
    int x, y;
    for (int i = 0; i < Q; i++){
        cin >> x >> y;
        x--;
        y--;
        q.push_back({i, {x, y}});
    }
    sort(q.begin(), q.end(), cmp);
    int l = 0, r = 0;
    add(a[0]);
    for (auto i:q){
        while (i.second.first < l){
            l--;
            add(a[l]);
        }
        while (r < i.second.second){
            r++;
            add(a[r]);
        }
        while (l < i.second.first){
            remove(a[l]);
            l++;
        }
        while (i.second.second < r){
            remove(a[r]);
            r--;
        }
        res[i.first] = ans;
    }
    for (int i = 0; i < Q; i++){
        cout << res[i] << "\n";
    }
}