[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;
}

  转载请注明: Sshwy's Blog [SDOI2009]HH 的项链

 上一篇
优先队列 | 二插堆 优先队列 | 二插堆
简介二叉堆的逻辑结构是一颗完全二叉树,然而它的实现却是用一维数组实现的。二叉堆分小根堆和大根堆。对于小根堆中的结点 x,其子树的所有结点键值均大于 x,即值越小的越靠近根结点,根结点的优先级最高。(大根堆同理)二叉堆常用于解决一些队列模拟问
2018.11.29
下一篇 
[POJ1845]Sumdiv [POJ1845]Sumdiv
分析对 a 分解质因数: a=\prod_{i=1}^k{p_i}^{c_i}于是 a 的因数和表示为 \sigma_a=\prod_{i=1}^{k}\left(\sum_{j=0}^{c_i}{p_i}^j\right)括号里是一个
2018.11.24
  目录