思路；

　　莫队；

 

代码：

#include 
     
      #define maxn 100005#define maxm 400005 #define maxnnum 2000005using namespace std;int bel[maxn];struct QueryType {    int l,r,id;    bool operator <(const QueryType pos)const    {        if(bel[l]==bel[pos.l]) return r
      
       '9'||Cget<'0')Cget=getchar();    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }}inline void updata(int x,bool di){    x=ai[x];    if(di)    {        if(!num[x]) now++;        num[x]++;    }    else    {        if(num[x]==1) now--;        num[x]--;    }}int main(){    in(n),blo=sqrt(n);    for(int i=1;i<=n;i++) in(ai[i]),bel[i]=(i+1)/blo;    in(m);    for(int i=1;i<=m;i++) in(qu[i].l),in(qu[i].r),qu[i].id=i;    sort(qu+1,qu+m+1);    int l=1,r=0;    for(int no=1;no<=m;no++)    {        while(r
       
        qu[no].r) updata(r--,false);        while(l
        
         qu[no].l) updata(--l,true);        ans[qu[no].id]=now;    }    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);    return 0;}