简要题意:
区间众数 强制在线 空间<n根号

区间众数的做法很普通
就是分根号块 预处理两块之间众数mx[i][j]，以及cnt[i][j]表示前i块中权值j出现次数
询问时要么众数是块间原本的众数 否则一定在多出来的里面出现过 时间n根号
由于cnt[i][j] 空间n根号

如何优化空间呢

特判掉出现次数<k的权值 这样cnt[i][j]中j就<=n/k 空间就变成n根号/k了

怎么特判呢 就是再用个l[k][i]表示出现次数=k时，右端点为i，第一次可以的那个左端点(也就是最大的那个)

我k取了3 (由于初始ans为清0，导致第一次就异或，wa了很久很久)

#include<cstdio>
#include<algorithm>
#include<string.h>
using std::sort;
using std::swap;

#define us unsigned short
#define gc getchar()
void read(us &x)
{
    char ch;
    while((ch=gc)<'0');
    for(x=ch-'0';(ch=gc)>='0';)x=x*10+ch-'0';
}
void read(int &x)
{
    char ch;
    while((ch=gc)<'0');
    for(x=ch-'0';(ch=gc)>='0';)x=x*10+ch-'0';
}

void chmax(us &x,us y)
{
    if(x<y)x=y;
}

#define B(i) ((i-1)/len)
const int K=240,N=60000,U=N/4+5;
us kl[K],kr[K];
us cnt[K][U],mx[K][K];
us n,m,i,j,l,len,k;
us a[N+5],top;bool del[N+5];
us now[U],st[N/K*2+10],stt,nowmx;
us dr[N+5],dl[N+5];
us l_2[N+5],l_3[N+5];//l_i[r]= 当右端点=[1,r]时，达到i需要的最大左端点 

struct item
{
    int a;us id;
    bool operator <(const item &i)const
    {
        return a<i.a;
    }
}q[N+5];
void mark(us l,us r)
{
    if(l>r)swap(l,r);
    del[l]=del[r]=1;chmax(l_2[r],l);
}
void mark(us a,us b,us c)
{
if(a>b)swap(a,b);
if(b>c)
{swap(b,c);
if(a>b)swap(a,b);
}
    del[a]=del[b]=del[c]=1;
    chmax(l_3[c],a);
    chmax(l_2[c],b);
    chmax(l_2[b],a);
}
void check(us i)
{
    if(i==1||(q[i].a!=q[i-1].a)) 
    {    
        del[q[i].id]=1; 
        --top;
    }else
    if(i==2||(q[i].a!=q[i-2].a)) 
    {
        mark(q[i].id,q[i-1].id); 
        --top;
    }else
    if(i==3||(q[i].a!=q[i-3].a))
    {
        mark(q[i].id,q[i-1].id,q[i-2].id);
        --top;
    }
}
void lisan()
{
    for(i=1;i<=n;++i){read(q[i].a);q[i].id=i;}
    sort(q+1,q+n+1);
    top=a[q[1].id]=0;
    for(i=2;i<=n;++i)
    {
     if(q[i].a!=q[i-1].a) 
     {
       check(i-1);++top;
     }
     a[q[i].id]=top;  
    }
    check(n);
}

void write(us x)
{
    putchar('-');
    for(;x;x/=10)st[++stt]=x%10;
    for(;stt;--stt)putchar('0'+st[stt]);
    putchar('\n');
}

us ql,qr,L,R;

int main()
{   freopen("1.in","r",stdin);freopen("2.out","w",stdout);
    read(n);read(m);
    lisan();

    us t=0;
    for(i=1;i<=n;++i)
    {
        if(del[i])dr[i]=t;
        else a[dr[i]=++t]=a[i];
    }
    dl[n+1]=++t;
    for(i=n;i;--i)
    {
        if(del[i])dl[i]=t;
        else dl[i]=--t;
    }
    t=dr[n];
    for(i=1;i<=n;++i) {chmax(l_2[i],l_2[i-1]);chmax(l_3[i],l_3[i-1]);}

    if(!t)
    {
        while(m--)
        {
            read(ql);read(qr);
                ql^=nowmx;qr^=nowmx;
            nowmx=(ql<=l_3[qr])?3:((ql<=l_2[qr])?2:1);
            write(nowmx);
        }
        return 0;
    }

    for(len=1;B(t)>=K||len<t/len;++len);
    kl[0]=1;
    for(i=len+1;i<=t;i+=len) {kr[B(i)-1]=i-1;kl[B(i)]=i;} 
    kr[k=B(t)]=t;

    for(i=0;i<=k;++i)
    {
        nowmx=0;
        for(j=i;j<=k;++j)
        {
          for(l=kl[j];l<=kr[j];++l)
          if(++now[a[l]]>nowmx)nowmx=now[a[l]];
          mx[i][j]=nowmx;
          if(!i)memcpy(cnt[j],now,(top+1)*2);
        }
        memset(now,0,(top+1)*2);
    }

    nowmx=0;
    while(m--)
    {
        read(ql);read(qr);
        ql^=nowmx;qr^=nowmx;
        L=B(dl[ql]);R=B(dr[qr]);
        if(L>=R) 
        {
            for(i=dl[ql];i<=dr[qr];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            nowmx=0;
            for(;stt;--stt) 
            {
              if(now[st[stt]]>nowmx)nowmx=now[st[stt]];
              now[st[stt]]=0;
            }
        }
        else
        {
            for(i=dl[ql];i<=kr[L];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            for(i=kl[R];i<=dr[qr];++i)
            if(++now[a[i]]==1) st[++stt]=a[i];
            nowmx=mx[L+1][R-1];
            for(;stt;--stt) 
            {
              us &x=now[st[stt]];
              x+=cnt[R-1][st[stt]]-cnt[L][st[stt]];
              if(x>nowmx)nowmx=x;
              x=0;
            }
        }
        if(nowmx<3)
        {
         if(ql<=l_3[qr])nowmx=3;
         else
         if(nowmx<2)
         {
           if(ql<=l_2[qr])nowmx=2;
           else
           if(nowmx<1)nowmx=1; 
         }
        }
        write(nowmx);
    }
}