HH的项链

· · 个人记录

旧题重温

水平有限，如有疏漏，墙裂欢迎提出
思路，代码借鉴题解
算法标签：树状数组，主席树

BZOJ原题

简要题意：多次询问区间不同数的个数

法一：

观察到数的范围是比较小的。多次询问很麻烦，不好把握询问间的关系，而如果能利用一些已经求过的答案，时间复杂度就会更优。所以先考虑让询问的右端点有序，也就是离线算法。在两次询问r之间的数就是本次加入的数。

①对于新加入的数a[i]，如果之前没有和它一样的数，那么就在i处放一标记

②如果之前有和它一样的数a[j]，我们就要删除其中一个：若a[j]在当前区间内，则a[i]一定也在区间内；若a[i]在当前区间内，那么a[j]不一定在区间内。综上，我们要舍弃a[j]保留a[i]，即删除在j处的标记，在i处添加标记

这样[l,r]的标记数就是答案，而a[j]可以预处理出来。于是我们需要一支持单点修改，区间求和的数据结构，即树状数组

\color{Fuchsia}\text{Talk is Cheap, Show Me the Code!}

口胡谁都会，我要看代码

\downarrow\ $见文末$^1

法二：

如果要求强制在线的话，我们需要考虑统计c=|\{i|i\in[l,r]\ \&\&\ last[i]\in[l,r]\}|，其中last[i]表示max\{j|j<i\ \&\&\ a[j]==a[i]\}，(区间长度-c)就是答案了

具体地，我们可以对last开桶，即记录bin[i]=|\{j|j\in[l,r]\ \&\&\ last[j]==i\}|，用主席树维护，每加入一个数就新开一个版本，c=\ \ r版本下\sum\limits_{i=l}^{r}bin[i]

\color{Fuchsia}\text{Talk is Cheap, Show Me the Code!}

口胡谁都会，我要看代码

\downarrow\ $见文末$^2

法一：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX=1000006;
struct query{
    int l,r,order,ans;
}h[MAX];
bool compare1(query a,query b){
    return a.r<b.r;
}
bool compare2(query a,query b){
    return a.order<b.order;
}
int last[MAX],head[MAX],tree[MAX];
int n,m;
inline int lowbit(int x){
    return x&(-x);
}
inline void modify(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))tree[i]+=y;
}
inline int sum(int x){
    if(x==0)return 0;
    int ret=0;
    for(int i=x;i;i-=lowbit(i))ret+=tree[i];
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int x,i=1;i<=n;i++){
        scanf("%d",&x);
        last[i]=head[x];
        head[x]=i;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&h[i].l,&h[i].r);
        h[i].order=i;
    }

    sort(h+1,h+m+1,compare1);
    for(int i=1;i<=m;i++){
        for(int j=h[i-1].r+1;j<=h[i].r;j++){
            if(last[j])modify(last[j],-1);
            modify(j,1);
        }
        h[i].ans=sum(h[i].r)-sum(h[i].l-1);
    }
    sort(h+1,h+m+1,compare2);
    for(int i=1;i<=m;i++)printf("%d\n",h[i].ans);
    return 0;
}

法二：

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX=1000006;
struct node{
    int l,r,ls,rs,value;
}h[MAX];
int cnt,cnt_head;
int last[MAX],head[MAX];
inline void pushup(int rt){
    h[rt].value=h[h[rt].ls].value+h[h[rt].rs].value;
}
int query(int now,int l,int r){
    if(l<=h[now].l && h[now].r<=r)return h[now].value;
    int mid=(h[now].l+h[now].r)>>1,ret=0;
    if(l<=mid)ret+=query(h[now].ls,l,r);
    if(mid<r)ret+=query(h[now].rs,l,r);
    return ret;
}
void build(int l,int r){
    int now=++cnt;
    h[now]=node{l,r};
    if(l==r)return ;
    int mid=(l+r)>>1;
    h[now].ls=cnt+1,build(l,mid);
    h[now].rs=cnt+1,build(mid+1,r);
}
void add(int replace,int now,int aim){
    h[now]=h[replace];
    if(h[now].l==h[now].r){
        h[now].value++;
        return ;
    }
    int mid=(h[now].l+h[now].r)>>1;
    if(aim<=mid){
        h[now].ls=++cnt;
        add(h[replace].ls,cnt,aim);
    }else{
        h[now].rs=++cnt;
        add(h[replace].rs,cnt,aim);
    }
    pushup(now);
}
int n,m;
int main(){
    scanf("%d",&n);
    build(0,n),head[0]=1;
    for(int x,i=1;i<=n;i++){
        scanf("%d",&x);
        head[++cnt_head]=++cnt;
        add(head[cnt_head-1],head[cnt_head],last[x]);
        last[x]=i;
    }
    scanf("%d",&m);
    for(int x,y,i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        printf("%d\n",y-x+1-query(head[y],x,y));
    }
    return 0;
}