給定一個固定的序列益楼，有多次查詢声离；每次查詢某個區(qū)間的元素集合信息(去除重復(fù)值項(xiàng))蚣抗。
由于是序列是固定的玖雁，故可以對所有查詢進(jìn)行離線處理缀旁，對查詢按照區(qū)間右端點(diǎn)從小到大排序记劈；按此順序處理查詢，在處理查詢之前維護(hù)好序列中各個值在本次查詢的右端點(diǎn)之前最后出現(xiàn)的位置并巍，我們只在最后出現(xiàn)的這個值的位置保留這個值目木，之前的位置都刪除；這樣區(qū)間查詢的時候就不會計算到重復(fù)的值項(xiàng)懊渡。用map映射某個值最后出現(xiàn)的位置刽射，用樹狀數(shù)組或者線段樹維護(hù)區(qū)間信息即可。
另外如果覺得map運(yùn)行速度太慢剃执，可以嘗試一種離散化處理的方法（當(dāng)然會不會比map快不好說誓禁，視具體情況而定）：
for (int i=1;i<=n;i++) {
scanf("%d", &a[i]);
b[i-1] = a[i]; //b數(shù)組最終用來存放不重復(fù)的數(shù)值
}
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;
//將原來數(shù)組元素賦值成該元素在b數(shù)組中的位置，這個位置當(dāng)作key來用
}
例題1
HDU-3333
求某個區(qū)間的不重復(fù)元素的和肾档。
#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]);
//如果之前出現(xiàn)過這個值现横，那么刪除
last[a[cnt]] = cnt;
//記錄最后出現(xiàn)的位置
update(1,1,n,cnt,a[cnt]);
//在當(dāng)前出現(xiàn)的位置加上這個值
}
ans[q[i].id] = query(1,1,n,q[i].l,q[i].r); //直接查詢區(qū)間和即可
}
for (int i=0;i<m;i++) printf("%I64d\n", ans[i]);
}
return 0;
}
例題2
Codeforces 703D
求某個區(qū)間不重復(fù)元素的異或和，跟上一題一樣的處理方法阁最，利用異或的性質(zhì)即可。
#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;
}
