题目链接
https://www.luogu.org/problem/P1972
分析
将询问离线，同时要用到树状数组。
先把询问按右端点升序排序，依次处理，此时对于重复出现的数，我们实际上只关心当前最靠右的。
AC代码
#include <cstdio>
#include <algorithm>
using namespace std;
inline int get_num() {
int num = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9')
num = num * 10 + c - '0', c = getchar();
return num;
}
const int maxn = 5e5 + 5, maxc = 1e6 + 5;
struct Question {
int l, r, id;
bool operator < (const Question& rhs) const {
return r < rhs.r;
}
} q[maxn];
int n, m, num[maxn], last[maxc], bit[maxn], ans[maxn];
inline int ask(int x) {
int sum = 0;
while (x) sum += bit[x], x -= x & (-x);
return sum;
}
inline void add(int x, int d) {
while (x <= n)
bit[x] += d, x += x & (-x);
}
int main() {
n = get_num();
for (int i = 1; i <= n; ++i) num[i] = get_num();
m = get_num();
for (int i = 1; i <= m; ++i)
q[i].l = get_num(), q[i].r = get_num(), q[i].id = i;
sort(q + 1, q + m + 1);
int j = 0;
for (int i = 1; i <= m; ++i) {
while (j < q[i].r) {
++j;
if (last[num[j]]) add(last[num[j]], -1);
add(j, 1);
last[num[j]] = j;
}
ans[q[i].id] = ask(q[i].r) - ask(q[i].l - 1);
}
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
