毒瘤题 hh的项链

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,sn,m,l=1,r,an,a[N],b[N],bel[N],ans[N];
struct ques{int l,r,id;} q[N];
inline bool cmp(ques a,ques b)
{
    if(bel[a.l]^bel[b.l])   return bel[a.l]<bel[b.l];
    if(bel[a.l]&1)  return a.r<b.r;
    return a.r>b.r;
}
inline void del(int i)
{
    b[a[i]]--;
    if(!b[a[i]])   an--;
}
inline void add(int i)
{
    if(!b[a[i]])   an++;
    b[a[i]]++;
}
inline int read()
{
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))	ch=getchar();
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
	return x;
}
signed main()
{
    n=read();
    sn=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        bel[i]=i/sn;
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].l=read();
		q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(l<q[i].l) del(l++);
        while(r>q[i].r) del(r--);
        while(l>q[i].l) add(--l);
        while(r<q[i].r) add(++r);
        ans[q[i].id]=an;
    }
    for(int i=1;i<=m;i++)   printf("%d\n",ans[i]);
    return 0;
}