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