题解（回滚莫队）

回滚莫队板子题之一。求区间众数是经典的添加易删除难，考虑回滚莫队。储存两个状态，一个是最小众数一个是最小众数的数量，两个变量一起回滚。其它细节是板子。跑得极快。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=600005;
int n,tot,B,T,b[N],cnt[N],a[N],ans[N],c[N],L,R,tmp,cur,num,tmpnum,bl[N],br[N],be[N];
struct qry{
    int l,r,id;
    bool operator<(const qry &y)const{return (be[l]^be[y.l])?l<y.l:r<y.r;}
}q[N];
int bf(int l,int r){
    int ans=2e9,num=0;
    for(int i=l;i<=r;++i)++c[a[i]];
    for(int i=l;i<=r;++i)if(num<c[a[i]]||(num==c[a[i]]&&a[i]<ans))num=c[a[i]],ans=a[i];
    for(int i=l;i<=r;++i)--c[a[i]];
    return ans;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),T=sqrt(n),B=n/T;
    for(int i=1;i<=n;++i)a[i]=b[i]=read();
    for(int i=1;i<=n;++i)q[i]={read(),read(),i};
    sort(b+1,b+n+1),tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    for(int i=1;i<=B;++i)bl[i]=br[i-1]+1,br[i]=bl[i]+T-1;
    if(br[B]<n)++B,bl[B]=br[B-1]+1,br[B]=n;
    for(int i=1;i<=n;++i)be[i]=(i-1)/T+1;
    sort(q+1,q+n+1);
    for(int i=1,idx=1;i<=B;++i){
        memset(cnt,0,sizeof cnt);
        R=br[i];
        tmp=2e9,tmpnum=0;
        while(idx<=n&&be[q[idx].l]==i){
            L=br[i]+1;
            if(q[idx].r-q[idx].l<=T){
                ans[q[idx].id]=bf(q[idx].l,q[idx].r);
                ++idx;
                continue;
            }
            while(q[idx].r>R){++cnt[a[++R]];if(tmpnum<cnt[a[R]]||(tmpnum==cnt[a[R]]&&a[R]<tmp))tmpnum=cnt[a[R]],tmp=a[R];}
            cur=tmp,num=tmpnum;
            while(q[idx].l<L){++cnt[a[--L]];if(tmpnum<cnt[a[L]]||(tmpnum==cnt[a[L]]&&a[L]<tmp))tmpnum=cnt[a[L]],tmp=a[L];}
            ans[q[idx].id]=tmp;
            tmp=cur,tmpnum=num;
            while(L<=br[i])--cnt[a[L++]];
            ++idx;
        }
    }
    for(int i=1;i<=n;++i)write(b[ans[i]]),putchar('\n');
    return 0;
}