本文主要是介绍SPOJ 3267 DQUERY——求区间内不重复值的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, …, aj.
Input
Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, …, an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).
Output
For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, …, aj in a single line.
Example
Input
5
1 1 2 1 3
3
1 5
2 4
3 5
Output
3
2
3
这个就是先离散化，在update的时候看看这个值有没有出现过，如果出现过，那就先把当前位置+1，再把上个位置-1，因为主席树是保存以前版本的，所以不用担心区间查询的时候会出问题。
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int sum[N*40],ls[N*40],rs[N*40],rt[N*40];
int tot,n,m;
int vis[N],a[N],b[N];
void update(int l,int r,int root,int last,int q,int val)
{sum[root]=sum[last]+val;ls[root]=ls[last];rs[root]=rs[last];if(l==r)return;int mid=l+r>>1;if(mid>=q)update(l,mid,ls[root]=++tot,ls[last],q,val);elseupdate(mid+1,r,rs[root]=++tot,rs[last],q,val);
}
int query(int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr)return sum[root];int mid=l+r>>1;int ans=0;if(mid>=ql)ans+=query(l,mid,ls[root],ql,qr);if(mid<qr)ans+=query(mid+1,r,rs[root],ql,qr);return ans;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+1+n);int all=unique(b+1,b+1+n)-(b+1);for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+all,a[i])-b;for(int i=1;i<=n;i++){if(!vis[a[i]])update(1,n,rt[i]=++tot,rt[i-1],i,1);else{update(1,n,rt[i]=++tot,rt[i-1],i,1);int del=++tot;update(1,n,del,rt[i],vis[a[i]],-1);rt[i]=del;}vis[a[i]]=i;}scanf("%d",&m);int l,r;while(m--){scanf("%d%d",&l,&r);printf("%d\n",query(1,n,rt[r],l,r));}return 0;
}
这篇关于SPOJ 3267 DQUERY——求区间内不重复值的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
