显示原始代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int n, q, a[N], t[N], vis[N], ans[N];
struct itv {
int l, r, num;
} id[N];
int read() {
int oup;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') oup = oup * 10 + c - '0';
return oup;
}
bool cmp(int x, int y) {
if (id[x].r == id[y].r)
return id[x].l < id[y].l;
return id[x].r < id[y].r;
}
int lowbit(int n) { return n & (-n); }
void modify(int a, int b) {
for (; a <= n; a += lowbit(a)) t[a] += b;
}
int sum(int rig) {
int cnt = 0;
for (; rig >= 1; rig -= lowbit(rig)) cnt += t[rig];
return cnt;
}
int main() {
n = read(), q = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= q; i++) id[i].l = read(), id[i].r = read();
for (int i = 1; i <= q; i++) id[i].num = i;
int p = 1;
for (int i = 1; i <= q; i++) {
for (int j = p; j <= id[i].r; j++) {
if (vis[a[j]])
modify(vis[a[j]], -1);
modify(j, 1);
vis[a[j]] = j;
}
p = id[i].r + 1;
ans[id[i].num] = sum(id[i].r) - sum(id[i].l - 1);
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
