HH的项链

延迟操作（离线）

分析：出现了新颜色，才能算贡献，如：{1，2，3，4，3，5}可以看作{1，1，0，1，1，1} ， 同一种颜色，位置更后的更优（对L来讲），所以当相同的颜色出些后，计算后者的贡献，并把前者产生的贡献抹除；而树状数组tr[i]维护的是位置i之前所有的贡献和

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) (x&(-x))
int const N=1e6+7;
int n,m;
int col[N],pre[N],ans[N];  //col[i]表示i位置对应的颜色，p[i]表示i颜色对应的位置 
struct L{
	int l,r,p;
}a[N];
bool cmp(L col,L a){
	return col.r<a.r;
}
ll tr[N<<2];
void add(int p,int w){
	for(;p<=n;p+=low(p)){
		tr[p]+=w;
	}
}
ll ask(int p){
	ll res=0;
	for(;p>0;p-=low(p)){
		res+=tr[p];
	}
	return res;
}
int main(){
	cin >> n;
	for(int i=1;i<=n;++i) cin >> col[i];
	cin >> m;
	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 nx=1;   //已经扫描到的位置 
	for(int i=1;i<=m;++i){
		for(int j=nx;j<=a[i].r;++j){
			if(pre[ col[j] ]) add(pre[col[j]],-1);	
			pre[col[j]]=j;
			add(pre[col[j]],1);
		}
		nx=a[i].r+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;
}