题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=32356
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.
题意：给出很多询问，求出每次询问数列中连续区间的不同的数的个数。
算法分析：算法思想是主席树，这个算法真是神奇得没话说，必须得崇拜呀。由于刚接触这个算法思想，所以主席树是参照kuangbin大牛的模板来写的。
引用主席树的发明人说过的两句话：
这个东西是当初我弱不会划分树的时候写出来替代的一个玩意..被一小撮别有用心的人取了很奇怪的名字> < 。
想法是对原序列的每一个前缀[1..i]建立出一颗线段树维护值域上每个数的出现次数，然后发现这样的树是可以减的，然后就没有然后了 。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define inf 0x7fffffff
using namespace std;
const int maxn=+;
const int M = maxn*+; int n,q,tot;
int an[maxn];
int T[maxn],lson[M],rson[M],c[M];
int build(int l,int r)
{
int root=tot++;
c[root]=;
if (l!=r)
{
int mid=(l+r)>>;
lson[root]=build(l,mid);
rson[root]=build(mid+,r);
}
return root;
}
int update(int root,int pos,int val)
{
int newroot=tot++,tmp=newroot;
c[newroot]=c[root]+val;
int l=,r=n;
while (l<r)
{
int mid=(l+r)>>;
if (pos<=mid)
{
lson[newroot]=tot++ ;rson[newroot]=rson[root];
newroot=lson[newroot] ;root=lson[root];
r=mid;
}
else
{
rson[newroot]=tot++ ;lson[newroot]=lson[root];
newroot=rson[newroot] ;root=rson[root];
l=mid+;
}
c[newroot]=c[root]+val;
}
return tmp;
}
int query(int root,int pos)
{
int ret=;
int l=,r=n;
while (pos<r)
{
int mid=(l+r)>>;
if (pos<=mid) {r=mid ;root=lson[root] ;}
else {ret += c[lson[root] ] ;root=rson[root] ;l=mid+ ;}
}
return ret+c[root];
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
tot=;
for (int i= ;i<=n ;i++) scanf("%d",&an[i]);
T[n+]=build(,n);
map<int,int> mp;
mp.clear();
for (int i=n ;i>= ;i--)
{
if (mp.find(an[i])==mp.end())
T[i]=update(T[i+],i,);
else
{
int tmp=update(T[i+],mp[an[i] ],-);
T[i]=update(tmp,i,);
}
mp[an[i] ]=i;
}
scanf("%d",&q);
while (q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(T[l],r));
}
}
return ;
}