Luogu | P1972 [高2021级考试 19.5.4] [SDOI 2009] HH的项链 | 数据结构 / 莫队 | 离线 / 线段树


Description

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……

因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。


Input Format

第一行:一个整数 $N$,表示项链的长度。

第二行:$N$ 个整数,表示依次表示项链中贝壳的编号(编号为 $0$ 到 $1000000$ 之间的整数)。

第三行:一个整数 $M$,表示 HH 询问的个数。

接下来 $M$ 行:每行两个整数,$L$ 和 $R$,表示询问的区间。


Output Format

$M$ 行,每行一个整数,依次表示询问对应的答案。


Input Sample

Sample 01

6
1 2 3 4 3 5
3
1 2
3 5
2 6


Output Sample

Sample 01

2
2
4


Data Range

$ 1 \le N,M \le 5 \times 10 ^ 5$。


Solution

对于右端点处于 $r$ 的询问,前 $r$ 个元素中只有最靠近 $r$ 的一个是有用的元素。考虑设 $l_i$ 表示颜色 $i$ 当前最后一次出现的位置。

则可以将所有询问按照右端点 $r$ 排序,用 线段树 / 树状数组 维护 “当前位置上的元素是否是一个独立的元素”,其中最靠近右端的一个元素视为独立元素,前面的元素视为重复元素。则对于每次排序后的询问,可以通过查询区间和来得到答案。

当然也可以可持久化线段树(不用离线)或者莫队。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm> 

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define LC lch[now]
#define RC rch[now]
#define mid ((L+R)>>1)

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct node{
    int lx,rx,id,ans;
    friend bool operator < (node a,node b){
        if(a.rx==b.rx) return a.lx<b.lx;
        return a.rx<b.rx;
    }
}q[500005];

int N,Q,ans,root,newp;
int src[500005],lch[1000005],rch[1000005],sumv[1000005],last[1000005];

bool s2(node a,node b){
    return a.id<b.id;
}

void upload(int now){
    sumv[now]=sumv[LC]+sumv[RC]; return;
}

void build(int &now,int L,int R){
    now=++newp; if(L==R) return;
    build(LC,L,mid); build(RC,mid+1,R);
}

void modify(int now,int L,int R,int pos,int val){
    if(L==R) {
        sumv[now]+=val; return;
    }if(pos<=mid) modify(LC,L,mid,pos,val);
    else modify(RC,mid+1,R,pos,val); upload(now);
}

int query(int now,int L,int R,int X,int Y){
    if(L>=X&&Y>=R) return sumv[now];
    if(Y<=mid) return query(LC,L,mid,X,Y);
    else if(X>mid) return query(RC,mid+1,R,X,Y);
    return query(LC,L,mid,X,Y)+query(RC,mid+1,R,X,Y);
}

void init(){
    Read(N);
    rep(i,1,N) Read(src[i]);
    Read(Q); return;
}

void solve(){
    rep(i,1,Q){
        Read(q[i].lx); Read(q[i].rx);
        q[i].id=i;
    }std::sort(q+1,q+1+Q);
    build(root,1,N);
    int j=1; rep(i,1,N){
        if(last[src[i]]==0) modify(root,1,N,i,1);
        else{
            modify(root,1,N,last[src[i]],-1);
            modify(root,1,N,i,1);
        }last[src[i]]=i;
        while(q[j].rx==i){
            q[j].ans=query(root,1,N,q[j].lx,q[j].rx);
            j++;
        }
    }
    std::sort(q+1,q+1+Q,s2);
    rep(i,1,Q) printf("%d\n",q[i].ans);
}

int main(){
    init();
    solve();
    return 0;
}