# 【題解】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();
}
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;
for (auto i:q){
while (i.second.first < l){
l--;
}
while (r < i.second.second){
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";
}
}
```