提交记录

#include <bits/stdc++.h>
#define rep(i,l,r) for(register int i(l);i^r+1;i=-(~i))
using namespace std;
const int N=2e6+5;
char *p1,*p2,buf[N];
struct query{
    int l,r,id;
}q[N];
#define getch() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
inline bool cmp1(register int x, register int y){
    return y-x>>31;
}
inline void read(register int &x){
    register char c (getchar());
    while(cmp1(48,c) | cmp1(c,57)) c = getchar();
    while((cmp1(48,c)^1) & (cmp1(c,57)^1)) x = (x<<1) + (x<<3) + (c^48),c = getchar();
}
inline void write(int i){
    if(cmp1(i,9))write(i / 10) ;
    putchar((i-i/10*10) | 0x30) ;
}
int n,m,a[N],ans[N],pos[N],cnt[N],l=1,r=0,rec=0,iidx,iiidx[N];
#define Add(x) rec+=(!cnt[a[x]]++)
#define Sub(x) rec-=(!(cnt[a[x]]--^1))
inline bool cmp(query &kkk,query &fusu){
	while(pos[kkk.l]^pos[fusu.l]) return cmp1(fusu.l,kkk.l);
	while(~pos[kkk.l]&1) return cmp1(kkk.r,fusu.r);	
	return cmp1(fusu.r,kkk.r);	
}
signed main(){
    read(n);
    rep(i,1,n){
        read(a[i]);
        if(!iiidx[a[i]])iiidx[a[i]]=(iidx=-(~iidx));
        a[i]=iiidx[a[i]];
    }
    read(m);
    register int siz=max(1,(int)(sqrt((double)(n)*n/(double)(m))));
    rep(i,1,m){
        read(q[i].l),read(q[i].r),q[i].id=i,pos[i]=i/siz;
    }
    sort(q+1,q+m+1,cmp);
    rep(i,1,m){
        while(cmp1(l,q[i].l))Add(--l);
        while(cmp1(q[i].r,r))Add(r=-(~r));
        while(cmp1(q[i].l,l))Sub(l),l=-(~l);
        while(cmp1(r,q[i].r))Sub(r),--r;
        ans[q[i].id]|=rec;
    }
    rep(i,1,m)write(ans[i]),putchar('\n');
    return 0;
}