提交记录

蒟蒻要split了

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;
const int mxn=708,maxn=5e5+5,smxn=maxn/mxn+5;

int n,len,kn[smxn],tot;
int kmx[smxn][smxn],bel[maxn];
int iskn[maxn];
int al[maxn];
int a[maxn],b[maxn],m;
int vis[maxn],vps[maxn];
vector<int> pos[maxn];

namespace quick {
#define tp template<typename Type>
    namespace in {
        inline char getc() {
            static char buf[1<<21],*p1=buf,*p2=buf;
            return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
        }
        inline int read(char *s) {
            *s=getc();
            while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
            while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
            *s='\0'; return 1;
        }
        tp inline int read(Type &x) {
            x=0;bool k=false;char c=getc();
            while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
            while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
            x*=(k?-1:1); return 1;
        }
        template <typename Type,typename... Args>
        inline int read(Type &t,Args &...args) {
            int res=0;
            res+=read(t);res+=read(args...);
            return res;
        }
    }
    using in::read;
    namespace out {
        char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
        inline void flush() {
            fwrite(buf,1,p1+1,stdout);
            p1=-1;
        }
        inline void putc(const char &c) {
            if(p1==p2) flush();
            buf[++p1]=c;
        }
        inline void write(char *s) {
            while(*s!='\0') putc(*s),s++;
        }
        tp inline void write(Type x) {
            static char buf[30];int p=-1;
            if(x<0) {putc('-');x=-x;}
            if(x==0) putc('0');
            else for(;x;x/=10) buf[++p]=x%10+48;
            for(;p!=-1;p--) putc(buf[p]);
        }
        inline void write(char c) {putc(c);}
        template <typename Type,typename... Args>
        inline void write(Type t,Args ...args) {
            write(t);write(args...);
        }
    }
    using out::write;
    using out::flush;
    tp inline Type max(const Type a,const Type b) {
        if(a<b) return b;
        return a;
    }
    tp inline Type min(const Type a,const Type b) {
        if(a<b) return a;
        return b;
    }
    tp inline void swap(Type &a,Type &b) {
        a^=b^=a^=b;
    }
    tp inline Type abs(const Type a) {
        return a>=0?a:-a;
    }
#undef tp
}
using namespace quick;

inline void update(int &a,int b)
{
    if(b>a) a=b;
}

int main()
{
    int t,pre=0;
    read(n,t);
    for(int i=1;i<=n;++i)
        read(a[i]),b[i]=a[i];
    tot=(n-1)/mxn+1;
    for(int i=1;i<=tot;++i)
        kn[i]=kn[i-1]+tot;
    kn[tot]=n;
    for(int i=1;i<=tot;++i)
        for(int j=kn[i-1]+1;j<=kn[i];++j)
            bel[j]=i;
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)
        al[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(int i=1;i<=tot;++i)
    {
        for(int j=i;j<=tot;++j)
        {
            int &nw=kmx[i][j];
            nw=kmx[i][j-1];
            for(int k=kn[j-1]+1;k<=kn[j];++k)
                update(nw,++vis[al[k]]);
        }
        memset(vis,0,sizeof(vis));
    }
    for(int i=1;i<=n;++i)
    {
        pos[al[i]].push_back(i);
        vps[i]=pos[al[i]].size()-1;
    }
    int l,r;
    while(t--)
    {
        read(l,r);
        l^=pre;r^=pre;
        int pl=bel[l],pr=bel[r];
        if(pl==pr)
        {
            int nowans=0;
            for(int i=l;i<=r;++i)
                update(nowans,++vis[al[i]]);
            for(int i=l;i<=r;++i)
                vis[al[i]]=0;
            write(nowans,'\n');
            pre=nowans;
        }
        else
        {
            int nowans=kmx[pl+1][pr-1];
            for(int i=l;i<=kn[pl];++i)
            {
                int siz=pos[al[i]].size();
                while(vps[i]+nowans<siz&&pos[al[i]][vps[i]+nowans]<=r) ++nowans;
            }
            for(int i=kn[pr-1]+1;i<=r;++i)
                while(vps[i]-nowans>=0&&pos[al[i]][vps[i]-nowans]>=l) ++nowans;
            write(nowans,'\n');
            pre=nowans;
        }
    }
    flush();
    return 0;
}

前面是优化，不用管