本文共 3631 字，大约阅读时间需要 12 分钟。
English Vietnamese
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
好久之前就做了这个题目了，但是一直没有写篇博客，也是因为一直不太理解吧。
查询区间有多少种数，查询次数 和 数列长度 都很大。一开始想有没有前缀和的关系，大失所望，没有。。例如 1 2 2 1 3 1位置和4位置都有1 1 到 3 有 2 种数 1 到 5 有 3 种数 ，那相减就是 4 到 5 有1种数 答案显然是2种数 因为 前面的区间和后面的区间有相同的数 ，这样相减就会忽略后面的数。所以我们要对 m 次查询进行离线化 ，按右边界r从小到大进行排序 然后数列中相同的数只保留最后一次出现的位置 ，之前出现过的位置的c值就要-1。这样就不用遍历n*q遍了。
代码如下：
#include #define ll long longusing namespace std;const int maxx=2e5+100;struct node{ int id; int l; int r; bool operator <(const node &a)const{ return a.r>r; }}p[maxx];map mp;int a[maxx],c[maxx],ans[maxx];int n,m;inline void init(){ mp.clear(); memset(c,0,sizeof(c));}inline int lowbit(int x){ return x&(-x);}inline void update(int cur,int v){ while(cur<=maxx) c[cur]+=v,cur+=lowbit(cur);}inline int query(int cur){ int sum=0;while(cur>0) sum+=c[cur],cur-=lowbit(cur);return sum;}int main(){ while(~scanf("%d",&n)) { init(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i; sort(p+1,p+1+m); int cnt=1; for(int i=1;i<=m;i++) { for(int j=cnt;j<=p[i].r;j++) { if(mp[a[j]]) update(mp[a[j]],-1); mp[a[j]]=j; update(j,1); } cnt=p[i].r+1; ans[p[i].id]=query(p[i].r)-query(p[i].l-1); } for(int i=1;i<=m;i++) printf("%d%c",ans[i],'\n'); } return 0;}
这是树状数组||线段树+离线做法。
主席树也可以求区间种类数。因为主席树把之前各个历史版本都能保存下来，这样我们就不用离线做了，就可以直接在线做了。但是还是如果之前出现过了，就在之前的版本减一，在当前版本加一。然后再右端点这个版本求（l,r）的种类数。
代码如下：
#include #include #include using namespace std; const int maxn = 30000 + 10;int n,q;int cnt = 0;struct Node{ int l,r,sum;}p[maxn*40];int la[1000000 + 10];int a[maxn];int root[maxn];int build(int l,int r){ int nc = ++cnt; p[nc].sum = 0; p[nc].l = p[nc].r = 0; if (l == r) return nc; int m = l + r >> 1; p[nc].l = build(l,m); p[nc].r = build(m+1,r); return nc;} int update(int pos,int c,int v,int l,int r){ int nc = ++cnt; p[nc] = p[c]; p[nc].sum += v; if (l == r) return nc; int m = l+r>>1; if (m >= pos){ p[nc].l = update(pos,p[c].l,v,l,m); } else { p[nc].r = update(pos,p[c].r,v,m+1,r); } return nc;} int query(int pos,int c,int l,int r){ if (l == r) return p[c].sum; int m = l + r >> 1; if (m >= pos) { return p[p[c].r].sum + query(pos,p[c].l,l,m); } else return query(pos,p[c].r,m+1,r);} int main(){ scanf("%d",&n); memset(la,-1,sizeof la); for (int i = 1; i <= n; ++i) { scanf("%d",a+i); } root[0] = build(1,n); for (int i = 1 ; i <= n; ++i) { int v = a[i]; if (la[v] == -1) { root[i] = update(i,root[i-1],1,1,n); } else { int t = update(la[v],root[i-1],-1,1,n); root[i] = update(i,t,1,1,n); } la[v] = i; } scanf("%d",&q); while(q--) { int x,y; scanf("%d %d",&x, &y); printf("%d\n",query(x,root[y],1,n)); } return 0;}
努力加油a啊，(o)/~
转载地址：http://nztvi.baihongyu.com/