一、题目大意
给你一个长度为 \(n\) 的颜色序列和 \(m\) 个询问，求每个询问区间中出现 \(2\) 次及以上的颜色种类数。
二、解题思路
我们仿照HH的项链一题的思路，设 \(pre_i\) 表示第 \(i\) 个点前面首个与 i 颜色相同的点的编号，\(end_i\) 表示第 \(i\) 个点后面首个与 i 颜色相同的点的编号。
然后定义一个点 i 在区间询问 [l,r] 中有贡献的条件为：
- prei 》= l（满足”出现 \(2\) 次及以上“的条件）
- i 为满足 1 条件的所有元素中下标最小的一个。（这样答案就保证是种类数）
这样问题就转化为了：求询问区间中有贡献的点的个数是多少。
根据上面的条件，再想到题目中是多组区间询问，于是使用离线二维数点来解决。
三、具体方法
使用树状数组维护，将有贡献的点标为 1，无贡献的点标为 0。
- 将询问离线，并从左到右遍历序列。
- 如果遇到左端点，算出左端点所对应的区间的总和（等价于有贡献的点的数量）。
- 每离开一个点，就将 end【i】标为 0，将 end【end【i】】标为 1（具体解释见下）。
四、对于第 3 点的解释
五、AC 代码
点击查看 AC 代码
#include <bits/stdc++.h>
using namespace std;const int N = 2e6 + 10;struct node{int id,num;
};vector<node> g[N];
int n,c,m,l,r,a[N],k[N],tr[N],num[N],ans[N];void add(int x,int c){for(;x <= n;x += x & (-x)) tr[x] += c;
}int sum(int x){int res = 0;for(;x > 0;x -= x & (-x)) res += tr[x];return res;
}int main(){scanf("%d %d %d",&n,&c,&m);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);for(int i = n;i >= 1;i--)k[i] = num[a[i]],num[a[i]] = i;for(int i = 1;i <= m;i++){scanf("%d %d",&l,&r);g[l].push_back(node{i,r});}for(int i = 1;i <= c;i++)if(k[num[i]]) add(k[num[i]],1);for(int i = 1;i <= n;i++){for(node j : g[i])ans[j.id] += sum(j.num) - sum(i - 1);if(k[i]) add(k[i],-1);if(k[k[i]]) add(k[k[i]],1);}for(int i = 1;i <= m;i++)printf("%d\n",ans[i]);return 0;
}