显示原始代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 500000 + 5;
const int maxm = maxn * 40;
int n, T, a[maxn], rt[maxn];
int L[maxm], R[maxm], sum[maxm], tot = 0;
int la[maxn + maxn + 1];
int build(int l, int r) {
int pos = ++tot;
sum[pos] = L[pos] = R[pos] = 0;
if (l < r) {
int mid = (l + r) >> 1;
L[pos] = build(l, mid);
R[pos] = build(mid + 1, r);
}
return pos;
}
int update(int pre, int idx, int v, int l, int r) {
int pos = ++tot;
L[pos] = L[pre];
R[pos] = R[pre];
sum[pos] = sum[pre] + v;
if (l < r) {
int mid = (l + r) >> 1;
if (idx <= mid)
L[pos] = update(L[pre], idx, v, l, mid);
else
R[pos] = update(R[pre], idx, v, mid + 1, r);
}
return pos;
}
int query(int idx, int pre, int l, int r) {
if (l == r)
return sum[pre];
int mid = (l + r) >> 1;
if (idx <= mid)
return query(idx, L[pre], l, mid) + sum[R[pre]];
else
return query(idx, R[pre], mid + 1, r);
}
int main(void) {
scanf("%d%d", &n, &T);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
memset(la, -1, sizeof(la));
rt[0] = build(1, n);
for (int i = 1; i <= n; ++i) {
int v = a[i];
if (la[v] == -1) {
rt[i] = update(rt[i - 1], i, 1, 1, n);
} else {
int t = update(rt[i - 1], la[v], -1, 1, n);
rt[i] = update(t, i, 1, 1, n);
}
la[v] = i;
}
while (T--) {
int x, y;
scanf("%d%d", &x, &y);
cout << query(x, rt[y], 1, n) << endl;
}
return 0;
}