显示原始代码
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxN = 2e5 + 10;
int a[maxN], num[1000010];
vector<pair<int, int>> query(maxN);
void solve() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
query[i] = make_pair(l, r);
}
sort(query.begin(), query.begin() + q, [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
});
int ans = 0;
for (int i = query[0].first; i <= query[0].second; i++) {
if (!num[a[i]])
ans++;
num[a[i]]++;
}
cout << ans << endl;
for (int i = 1; i < q; i++) {
int r = min(query[i - 1].second, query[i].first - 1);
for (int j = query[i - 1].first; j <= r; j++) {
num[a[j]]--;
if (!num[a[j]])
ans--;
}
int l = max(query[i - 1].second + 1, query[i].first);
for (int j = l; j <= query[i].second; j++) {
if (!num[a[j]])
ans++;
num[a[j]]++;
}
cout << ans << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}