版权声明:本文为博主原创文章,未经博主允许不得转载。
题意:
给出一串数,询问[L,R]区间中有多少个不同的数 。
解法:
关键是查询到某个右端点时,使其左边出现过的数都记录在它们出现的最右位置置1,其他位置置0,然后直接统计[L,R]的区间和就行了。
在线和离线都可以做 。
话不多说,上代码 。
在线主席树
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#define ll long long using namespace std; const int N=+;
const int M=+; int Ls[N*],Rs[N*],sum[N*],root[N];
int tot=; int pos[M];
int a[N];
int n,q; inline void copy(int x,int y){
Ls[x]=Ls[y];
Rs[x]=Rs[y];
sum[x]=sum[y];
} inline int bulidtree(int L,int R){
if (L>R) return ;
int k=tot++;
sum[k]=;
if (L==R) return k;
int mid=(L+R)>>;
Ls[k]=bulidtree(L,mid);
Rs[k]=bulidtree(mid+,R);
return k;
} inline int update(int o,int p,int v,int L,int R){
int k=tot++;
copy(k,o);
sum[k]+=v; if (L==R) return k; int mid=(L+R)>>;
if (p<=mid) Ls[k]=update(Ls[k],p,v,L,mid);
else Rs[k]=update(Rs[k],p,v,mid+,R); return k;
} inline int query(int o,int x,int y,int L,int R){
if (L==x && R==y) return sum[o];
int mid=(L+R)>>;
if (y<=mid) return query(Ls[o],x,y,L,mid);
else if (x>mid) return query(Rs[o],x,y,mid+,R);
else return query(Ls[o],x,mid,L,mid)+query(Rs[o],mid+,y,mid+,R);
} int main(){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",a+i); root[]=bulidtree(,n); memset(pos,-,sizeof(pos));
for (int i=;i<=n;i++){
root[i]=root[i-];
if (~pos[a[i]])
root[i]=update(root[i],pos[a[i]],-,,n);
root[i]=update(root[i],i,,,n);
pos[a[i]]=i;
} scanf("%d",&q);
int x,y;
while (q--){
scanf("%d %d",&x, &y);
printf("%d\n",query(root[y],x,y,,n));
} return ;
}
离线树状数组
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#define ll long long using namespace std; const int N=;
const int Q=;
const int M=; struct query{
int L,R;
int id;
bool operator < (const query & t) const {
return R<t.R;
}
}q[Q]; int a[N];
int pos[M]={};
int ans[Q]; int c[N]; // 树状数组
int n; inline int lowbit(int x){
return x&(-x);
} inline void add(int x,int d){
while (x<=n) {
c[x]+=d;
x+=lowbit(x);
}
} inline int sum(int x){
int ret=;
while (x){
ret+=c[x];
x-=lowbit(x);
}
return ret;
} int main(){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",a+i); int m;
scanf("%d",&m);
for (int i=;i<=m;i++) scanf("%d %d",&q[i].L, &q[i].R),q[i].id=i;
sort(q+,q++m); int j=;
for (int i=;i<=n;i++){
if (pos[a[i]]) add(pos[a[i]],-);
add(i,);
pos[a[i]]=i; while (j<=m && q[j].R==i){
ans[q[j].id]=sum(q[j].R)-sum(q[j].L-);
j++;
}
} for (int i=;i<=m;i++) printf("%d\n",ans[i]); return ;
}