RT

卡了30次了

$58\rightarrow72$

真不会卡了啊qaq

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <sys/mman.h>
using namespace std;
struct _io {
    char* s;
    _io() : s((char*)mmap(0, 1 << 25, PROT_READ, MAP_PRIVATE, fileno(stdin), 0)) {}
    operator int() {
        int x = 0,w=0;
        while((*s)<'0') w|=(!((*s)^45)),++s;
        while((*s)>='0') x=(x<<3)+(x<<1)+((*s++)&15);
        return x*(w?-1:1);
    }
} it;
#define read() it
inline void write(int x)
{
	if (x < 0) x = ~x + 1, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

struct qry
{
    int l,r,rk;
}q[1000010];

int n,m;
int a[1000010];
int bl[1000010];
int ans[1000010];
int b[1000010];
int num;

bool cmp(qry x,qry y)
{
    return (bl[x.l]^bl[y.l])?bl[x.l]<bl[y.l]:((bl[x.l]&1)?x.r<y.r:x.r>y.r);
}

int l=0,r=0;

void add(int p)
{
    if (b[a[p]]==0) ++num;
    ++b[a[p]];
}

void sub(int p)
{
    --b[a[p]];
    if (!b[a[p]]) num--;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    int blo=2134;
    for (int i=1;i<=n;i++)
    {
        bl[i]=(i-1)/blo+1;
    }
    m=read();
    for (int i=1;i<=m;i++)
    {
        q[i].l=read();
        q[i].r=read();
        q[i].rk=i;
    }
    sort(q+1,q+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        while (q[i].l<l) add(--l);
        while (q[i].r>r) add(++r);
        while (l<q[i].l) sub(l++);
        while (r>q[i].r) sub(r--);
        ans[q[i].rk]=num;
    }
    for (int i=1;i<=m;i++)
    {
        write(ans[i]);
        putchar('\n');
    }
}