显示原始代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 1000010
using namespace std;
int N, Q;
int a[maxn], ans[maxn];
int vis[maxn], tree[maxn];
struct QUE {
int l;
int r;
int id;
} q[maxn];
bool cmp(const QUE& a, const QUE& b) { return a.r < b.r; }
int lowbit(int x) { return x & (-x); }
void modify(int p, int v) {
for (; p <= N; p += lowbit(p)) tree[p] += v;
}
int query(int p) {
int res = 0;
for (; p; p -= lowbit(p)) res += tree[p];
return res;
}
int main() {
cin >> N >> Q;
for (int i = 1; i <= N; ++i) cin >> a[i];
for (int i = 1; i <= Q; ++i) {
cin >> q[i].l;
cin >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + Q + 1, cmp);
int pow = 1;
for (int i = 1; i <= Q; ++i) {
for (int j = pow; j <= q[i].r; ++j) {
if (vis[a[j]])
modify(vis[a[j]], -1);
modify(j, 1);
vis[a[j]] = j;
}
pow = q[i].r + 1;
ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
}
for (int i = 1; i <= Q; ++i) cout << ans[i] << endl;
return 0;
}