记录编号	246855	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	2.083 s
提交时间	2016-04-07 12:34:38	内存使用	7.56 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
#define MAXM 200010
struct node
{
    int l,r,id;
}q[MAXM];
int pos[MAXN],color[MAXN],sum[1000010],ans[MAXM];
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
bool cmp(node aa,node bb)
{
    if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
    return aa.l<bb.l;
}
int main()
{
    freopen("diff.in","r",stdin);
    freopen("diff.out","w",stdout);
    int n,block,i,m,tot,L,R;
    n=read();
    block=(int)sqrt(n);
    for(i=1;i<=n;i++)color[i]=read();
    m=read();
    for(i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
    for(i=1;i<=n;i++)pos[i]=(i-1)/block+1;
    sort(q+1,q+m+1,cmp);
    L=1;R=0;tot=0;
    memset(sum,0,sizeof(sum));
    for(i=1;i<=m;i++)
    {
        while(L<q[i].l)
        {
            sum[color[L]]--;
            if(sum[color[L]]==0)tot--;
            L++;
        }
        while(L>q[i].l)
        {
            L--;
            sum[color[L]]++;
            if(sum[color[L]]==1)tot++;
        }
        while(R<q[i].r)
        {
            R++;
            sum[color[R]]++;
            if(sum[color[R]]==1)tot++;
        }
        while(R>q[i].r)
        {
            sum[color[R]]--;
            if(sum[color[R]]==0)tot--;
            R--;
        }
        ans[q[i].id]=tot;
    }
    for(i=1;i<=m;i++)printf("%d\n",ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}