记录编号	400535	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.143 s
提交时间	2017-04-30 16:10:04	内存使用	51.03 MiB

#include<cstdio>
#define N 100005
using namespace std;
int cnt,n,m,a[N],next[N],head[10*N],sum[40*N];
int lon[40*N],ron[40*N],root[N],ll,rr;
void build(int &u,int l,int r)
{
     u=++cnt;
     if(l==r) return;
     int m=(l+r)/2;
     build(lon[u],l,m);
     build(ron[u],m+1,r);
}
void update(int p,int &u,int l,int r,int x)
{
     u=++cnt;
     sum[u]=sum[p]+1;
     lon[u]=lon[p]; ron[u]=ron[p];
     if(l==r) return;
     int m=(l+r)/2;
     if(x<=m)
       update(lon[p],lon[u],l,m,x);
     if(x>m) 
       update(ron[p],ron[u],m+1,r,x);
}
int query(int p,int u,int l,int r,int x)
{
    if(x>=r) return sum[u]-sum[p];
    if(x<l) return 0;
    int m=(l+r)/2;
    return query(lon[p],lon[u],l,m,x)+query(ron[p],ron[u],m+1,r,x);
}
int main()
{
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
      scanf("%d",&a[i]);
      next[i]=head[a[i]];
      head[a[i]]=i;
    }
    build(root[0],0,n);
    for(int i=1;i<=n;i++)
      update(root[i-1],root[i],0,n,next[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
      scanf("%d%d",&ll,&rr);
      printf("%d\n",query(root[ll-1],root[rr],0,n,ll-1));
    }
    //while(1);
    return 0;
}