[HEOI2012]采花（树状数组维护贡献之和）

参考博客

分析：此题要出现了两个及以上的数量才算贡献，{1，2，2，3，1}可以看作{1，1，0，0，0}，当一种颜色出些两个以上时，对其出现的倒数第二个位置计算贡献；树状数组维护的是贡献之和

第一次抖过去

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) (x&(-x))
int const N=2e6+7;
struct L{
	int l,r,p;
}a[N];
inline bool const cmp(const L& a,const L& b){
	return a.r<b.r;
}
int n,c,m;
int tr[N<<2];
inline void add(int p,int const w){
	for(;p<=n;p+=low(p)){
		tr[p]+=w;
	}
}
inline int ask(int p){
	int res=0;
	for(;p>0;p-=low(p)){
		res+=tr[p];
	}
	return res;
}
int col[N],pre[N],pre2[N],ans[N];  //pre[i]表示颜色i的上一个位置在哪，pre2[i]则表示上上次在哪
int main(){
	cin >> n >> c >> m;
	for(int i=1;i<=n;++i) cin >> col[i];
	for(int i=1;i<=m;++i){
		cin >> a[i].l >> a[i].r;
		a[i].p=i;
	}
	sort(a+1,a+m+1,cmp);
	int j=1;
	for(int i=1;i<=m;++i){
		for(;j<=a[i].r;++j){
			if(pre2[ col[j] ]){
				add(pre2[ col[j] ],-1);
			}
			pre2[col[j]]=pre[col[j]];pre[col[j]]=j;
			if(pre2[col[j]]) add(pre2[col[j]],1);
		}
		ans[a[i].p]=ask(a[i].r)-ask(a[i].l-1);
	}
	for(int i=1;i<=m;++i) cout << ans[i] << "\n";
	return 0;
}