好奇怪的人物名字
和这道题的树状数组解法思想相同
我们要找区间中至少出现了两次的颜色，则区间内第一次出现的颜色没有价值，只有第二次出现的颜色才会对答案有所贡献。
先预处理出各个位置nex[i]，表示下一个该位置上的颜色出现的位置。
将询问按左端点排序，对于一个询问，从左向右枚举到左端点(-1)
对于当前枚举到的节点(i)，将它剔除，因为(i)被剔除，nex[i]就变成了第一次出现的位置，所以将它的贡献减去，而nex[nex[i]]变成了第二次出现的位置，需要将它的贡献加上
用树状数组维护，答案就是sum(r) - sum(l-1)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define lb (i & -i)
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
int n, c, m, tree[2000010];
inline void add(int x, int k) {
for(int i = x; i <= n; i += lb)
tree[i] += k;
}
inline int sum(int x) {
int ans = 0;
for(int i = x; i; i -= lb)
ans += tree[i];
return ans;
}
int col[2000010], nex[2000010], pos[2000010];
struct zzz {
int l, r, tim;
}q[2000010];
bool cmp(zzz x, zzz y) {
return x.l < y.l;
}
int ans[2000010];
int main() {
n = read(), c = read(), m = read();
for(int i = 1; i <= n; ++i) col[i] = read();
for(int i = n; i; --i)
nex[i] = pos[col[i]], pos[col[i]] = i;
for(int i = 1; i <= c; ++i)
if(pos[i] && nex[pos[i]]) add(nex[pos[i]], 1);
for(int i = 1; i <= m; ++i)
q[i].l = read(), q[i].r = read(), q[i].tim = i;
sort(q+1, q+m+1, cmp);
int l = 1;
for(int i = 1; i <= m; ++i) {
for(; l < q[i].l; ++l) {
if(nex[l]) add(nex[l], -1);
if(nex[nex[l]]) add(nex[nex[l]], 1);
}
ans[q[i].tim] = sum(q[i].r) - sum(q[i].l-1);
}
for(int i = 1; i <= m; ++i) printf("%d
", ans[i]);
return 0;
}