记录编号	422504	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	1.031 s
提交时间	2017-07-09 20:13:50	内存使用	3.30 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int M=50000+10;
const int N=200000+10;
const int qrt=230;
int val[M],block[M],cnt[M],ans[N];
int n,m,nt,an;
map<int,int> mp;
struct DATE{
       int l,r,id;
}a[N];
inline int read(){
       int x=0,f=1;char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
       while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
       return x*f;
}
bool cmp(DATE x,DATE y){
     if(block[x.l]==block[y.l])
       return x.r<y.r;
     return block[x.l]<block[y.l];
}
inline void update(int pos,bool pd){
    if(pd){
      cnt[val[pos]]++;
      if(cnt[val[pos]]==1)
        an++;
    }
    else{
      cnt[val[pos]]--;
      if(cnt[val[pos]]==0)
        an--;
    }
}
int DK(){
    freopen("diff.in","r",stdin);
    freopen("diff.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
      val[i]=read();
      block[i]=(i-1)/qrt+1;
      if(!mp.count(val[i])){
        nt++;
        mp[val[i]]=nt;
        val[i]=nt;
      }
      else
        val[i]=mp[val[i]];
    }
    m=read();
    for(int i=1;i<=m;i++){
      a[i].l=read();
      a[i].r=read();
      a[i].id=i;
    }
    sort(a+1,a+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
      for(;r<a[i].r;r++)
        update(r+1,1);
      for(;r>a[i].r;r--)
        update(r,0);
      for(;l<a[i].l;l++)
        update(l,0);
      for(;l>a[i].l;l--)
        update(l-1,1);
      ans[a[i].id]=an;
    }
    for(int i=1;i<=m;i++)
      printf("%d\n",ans[i]);
    //while(1);
    return 0;
}
int dk=DK();
int main(){
    ;
}