给定一个固定的序列，有多次查询；每次查询某个区间的元素集合信息(去除重复值项)。
由于是序列是固定的，故可以对所有查询进行离线处理，对查询按照区间右端点从小到大排序；按此顺序处理查询，在处理查询之前维护好序列中各个值在本次查询的右端点之前最后出现的位置，我们只在最后出现的这个值的位置保留这个值，之前的位置都删除；这样区间查询的时候就不会计算到重复的值项。用map映射某个值最后出现的位置，用树状数组或者线段树维护区间信息即可。
另外如果觉得map运行速度太慢，可以尝试一种离散化处理的方法（当然会不会比map快不好说，视具体情况而定）：
for (int i=1;i<=n;i++) {
scanf("%d", &a[i]);
b[i-1] = a[i]; //b数组最终用来存放不重复的数值
}
sort(b,b+n);
int nb = unique(b,b+n)-b;
for (int i=1;i<=n;i++){
a[i] = lower_bound(b,b+nb,a[i])-b;
//将原来数组元素赋值成该元素在b数组中的位置，这个位置当作key来用
}
例题1
HDU-3333
求某个区间的不重复元素的和。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
#define N 100005
struct que{
int l,r,id;
}q[N];
bool cmp(que a, que b){
return a.r<b.r;
}
long long tree[N<<2];
long long ans[N];
int a[N];
void update(int p,int l,int r,int pos,int val){
if (l==r){
tree[p] += val;
}
else{
int m = (l+r)>>1;
if (pos<=m) update(p<<1,l,m,pos,val);
else update(p<<1|1,m+1,r,pos,val);
tree[p] = tree[p<<1]+tree[p<<1|1];
}
}
long long query(int p,int l,int r,int L,int R){
if (L<=l&&r<=R){
return tree[p];
}
else{
int m = (l+r)>>1;
long long ret = 0;
if (L<=m) ret += query(p<<1,l,m,L,R);
if (R>m) ret += query(p<<1|1,m+1,r,L,R);
return ret;
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
int n,m;
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i=0;i<m;i++){
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q,q+m,cmp);
map<int,int> last;
int cnt = 0;
memset(tree,0,sizeof(tree));
for (int i=0;i<m;i++){
while(cnt+1<=q[i].r){
cnt++;
if (last[a[cnt]]) update(1,1,n,last[a[cnt]],-a[cnt]);
//如果之前出现过这个值，那么删除
last[a[cnt]] = cnt;
//记录最后出现的位置
update(1,1,n,cnt,a[cnt]);
//在当前出现的位置加上这个值
}
ans[q[i].id] = query(1,1,n,q[i].l,q[i].r); //直接查询区间和即可
}
for (int i=0;i<m;i++) printf("%I64d\n", ans[i]);
}
return 0;
}
例题2
Codeforces 703D
求某个区间不重复元素的异或和，跟上一题一样的处理方法，利用异或的性质即可。
#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
#define N 1000005
struct que{
int l,r,id;
}q[N];
bool cmp(que a,que b){
return a.r<b.r;
}
int tree[N<<2],sum[N],a[N],ans[N];
void update(int p,int l,int r,int pos,int val){
if (l==r) {
tree[p] = val;
}
else {
int m = (l+r)>>1;
if (pos<=m) update(p<<1,l,m,pos,val);
else update(p<<1|1,m+1,r,pos,val);
tree[p] = tree[p<<1]^tree[p<<1|1];
}
}
int query(int p,int l,int r,int L,int R){
if (L<=l&&r<=R) {
return tree[p];
}
else {
int m = (l+r)>>1;
int ret = 0;
if (L<=m) ret ^= query(p<<1,l,m,L,R);
if (R>m) ret ^= query(p<<1|1,m+1,r,L,R);
return ret;
}
}
int main(){
int n,m;
cin>>n;
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
sum[i] = sum[i-1]^a[i];
}
cin>>m;
for (int i=0;i<m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id = i;
}
sort(q,q+m,cmp);
int cnt = 0;
map<int,int> last;
for (int i=0;i<m;i++){
while(cnt+1<=q[i].r){
cnt++;
if (last[a[cnt]]) update(1,1,n,last[a[cnt]],0);
last[a[cnt]] = cnt;
update(1,1,n,cnt,a[cnt]);
}
ans[q[i].id] = sum[q[i].r]^sum[q[i].l-1]^query(1,1,n,q[i].l,q[i].r);
}
for (int i=0;i<m;i++) printf("%d\n",ans[i]);
return 0;
}
网友评论