spoj D-query

题解：

主席树

当一个数加入的时候，如果还没有出现过，就把0加一

如果出现过，就在最近出现的位置加一

查询的时候，查询以y为根，0-x-1 

减去以x-1 为根，0-x-1

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100005;
struct Tree
{
    int num,l,r,ls,rs;
}T[N*80];
int now,rt[N],la[N*10],n,m,cnt=1,x,y,k,a[N];
int build(int l,int r)
{
    now++;
    if (l==r)return now;
    int k=now,mid=(l+r)/2;
    if (l<=mid)T[k].ls=build(l,mid);
    if (mid<r)T[k].rs=build(mid+1,r);
    return k; 
}
int insert(int x,int l,int r,int s)
{
    now++;
    if (l==r)
     {
         T[now].num=T[x].num+1;
         return now;
     }
    int k=now,mid=(l+r)/2;
    if (s<=mid)
     {
         T[k].ls=insert(T[x].ls,l,mid,s);
         T[k].rs=T[x].rs;
     }
    else
     {
         T[k].ls=T[x].ls;
         T[k].rs=insert(T[x].rs,mid+1,r,s);
     } 
    T[k].num=T[T[k].ls].num+T[T[k].rs].num;
    return k; 
}
int find(int s,int x,int y,int l,int r)
{
    if (l>y||r<x)return 0;
    if (x<=l&&y>=r)return T[s].num;
    int ans=0,mid=(l+r)/2;
    if (x<=mid)ans+=find(T[s].ls,x,y,l,mid);
    if (y>mid)ans+=find(T[s].rs,x,y,mid+1,r);
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&m);
    rt[0]=build(0,n);
    for (int i=1;i<=n;i++)
     {
         if (!la[a[i]])rt[i]=insert(rt[i-1],0,n,0);
         else rt[i]=insert(rt[i-1],0,n,la[a[i]]);
         la[a[i]]=i;
     }
    while (m--)
     {
         scanf("%d%d",&x,&y);
         printf("%d
",find(rt[y],0,x-1,0,n)-find(rt[x-1],0,x-1,0,n));
     }
    return 0; 
}