题意：查找区间内不同数字的个数。
两种做法，一种是 树状数组离线，另一种就是主席树。
树状数组离线操作的链接 http://www.cnblogs.com/oneshot/p/4110415.html
两种方法思路差不多，都是扫一遍，如果这个数曾经出现过那么就 在上次位置-1，如果没有出现过就在 当前位置+1，同时更新该数字的最新的位置。
这样的话，在主席树里面 以x为根的线段树存的就是1-x之间不同的数字的个数。我们只需要查找以r为根的线段树同时大于l的区间内的个数就行了。
给主席跪了，orz。主席树其实就是每个位置对应一颗线段树，但是这样 n 个点 n 棵线段树显然会MLE，怎么解决呢？我们可以看到 从第 i 棵线段树到第i+1 棵线段树，很多子树都是相同的，这样如果再重新建一棵完整的线段树显然浪费了很大的空间。我们只需要把第i棵线段树的 某个子树同时第i+1棵线段树 某个 节点下面即可，这样就大大减小了空间复杂度。
#include <map>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3e4+;
int a[maxn],c[maxn*],lson[maxn*],rson[maxn*],tot,n,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++;
int tmp = newroot;
c[newroot] = c[root] + val;
int l = ,r = n;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
rson[newroot] = rson[root];
lson[newroot] = tot++;
newroot = lson[newroot];
root = lson[root];
r = mid;
}
else
{
lson[newroot] = lson[root];
rson[newroot] = tot++;
newroot = rson[newroot];
root = rson[root];
l = mid + ;
}
c[newroot] = c[root] + val;
}
return tmp;
}
int query(int root,int pos)
{
int res = ;
int l = ,r = n;
while (pos > l)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
res += c[rson[root]];
root = lson[root];
r = mid;
}
else
{
root = rson[root];
l = mid + ;
}
}
return res + c[root];
}
int per_root[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while (~scanf ("%d",&n))
{
tot = ;
for (int i = ; i <= n ;i++)
scanf ("%d",a+i);
per_root[] = build(,n);
map<int,int>mp;
for (int i = ; i <= n; i++)
{
if (mp.find(a[i]) == mp.end())
{
per_root[i] = update(per_root[i-],i,);
}
else
{
int tmp = update(per_root[i-],mp[a[i]],-);
per_root[i] = update(tmp,i,);
}
mp[a[i]] = i;
}
scanf ("%d",&m);
for (int i = ; i < m; i++)
{
int l,r;
scanf ("%d%d",&l,&r);
printf("%d\n",query(per_root[r],l));
}
}
return ;
}