166pts TLE #10 莫队求卡常

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#include<bits/stdc++.h>
using namespace std;
int pos[3000005],a[3000005],cnt[3000005],res,f[3000005];
struct query
{
    int l,r,id;
}q[3000005];
inline bool cmp(const query &x,const query &y)
{
    if(pos[x.l]!=pos[y.l])
        return pos[x.l]<pos[y.l];
    if(pos[x.l]&1)
        return x.r>y.r;
    return x.r<y.r;
}
inline void del(const int &x)
{
    --cnt[a[x]];
    if(!(cnt[a[x]]-1))
        --res;
}
inline void add(const int &x)
{
    ++cnt[a[x]];
    if(cnt[a[x]]==2)
        ++res;
}
inline int read()
{
    register int num=0;
    register bool flag=1;
    register char c;
    c=getchar_unlocked();
    while(!isdigit(c))
    {
        if(c=='-')
            flag=0;
        c=getchar_unlocked();
    }
    while(isdigit(c))
    {
        num=(num<<3)+(num<<1)+(c^48);
        c=getchar_unlocked();
    }
    return (flag?num:-num);
}
inline void write(int x)
{
    if(x==0)
    {
        putchar_unlocked('0');
        return;
    }
    if(x<0)
    {
        putchar_unlocked('-');
        x=-x;
    }
    char num[50];
    register int len=0;
    while(x)
    {
        num[len++]=(x%10)+'0';
        x/=10;
    }
    while(len--)
        putchar_unlocked(num[len]);
}
int main()
{
    register int n=read(),c=read(),block=sqrt(n),i,m=read(),l=1,r=0,x,tmp=0;
    int ans[3000005];
    for(i=1;i<=n;++i)
    {
        x=read();
        if(!f[x])
            f[x]=++tmp;
        a[i]=f[x];
        pos[i]=(i-1)/block+1;
    }
    for(i=1;i<=m;++i)
    {
        q[i].l=read();
        q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    register int ql,qr;
    for(i=1;i<=m;++i)
    {
        ql=q[i].l,qr=q[i].r;
        while(l<ql)
            del(l++);
        while(qr<r)
            del(r--);
        while(ql<l)
            add(--l);
        while(r<qr)
            add(++r);
        ans[q[i].id]=res;
    }
    for(i=1;i<=m;++i)
    {
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}