延迟操作(离线)
分析:出现了新颜色,才能算贡献,如:{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;
}