[SDOI2009]HH 的项链

题意

静态查询区间不同的数的个数

分析

对询问按右端点排序

对于每个元素，更新它最后出现的位置，然后区间求个数

树状数组维护即可

复杂度 .

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int n,m,a[N],ans[N];
int last[N*2];// 权值为 i 的数最后出现的位置

struct data{int l,r,idx;};
bool cmp(data x,data y){return x.r<y.r;}
data b[N];

int c[N];
void upd(int p,int x){for(int i=p;i<=n;i+=(i&-i))c[i]+=x;}
int ps(int p){
    int res=0;
    for(int i=p;i>0;i-=(i&-i))res+=c[i];
    return res;
}

int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].idx=i;
    sort(b+1,b+m+1,cmp);// 对询问排序
    int cur=1;
    for(int i=1;i<=n;i++){if(last[a[i]])upd(last[a[i]],-1);
        last[a[i]]=i;upd(i,1);//a[i] 最后一次出现的位置在 i
        while(b[cur].r<i)cur++;
        while(b[cur].r==i)ans[b[cur].idx]=ps(b[cur].r)-ps(b[cur].l-1),cur++;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}