题解
可以发现，对于区间([l,r])，只有整块中的众数与不被整块包含的数有成为该区间众数的可能（共(2cdot 块长+1)个）。因此预处理出(f[i][j])表示块编号([i,j])区间内的众数，具体实现：将(a)数组离散化，设(tmp)数组存储每个数出现的次数，枚举(i,j)，用(j)中元素更新(tmp)（每个(i)仅需一个(tmp)数组）。设vector数组(pos[i][])表示数(i)出现的位置（升序），对于可能为区间众数的(i)，二分(pos[i][])在区间([l,r])中的元素下标极值，即可求出(i)在([l,r])中出现的次数。若块长为(sqrt n)，则该算法时间复杂度为(O(nsqrt n logn))，且常数并不优秀，会TLE(´。＿。｀)。但是查询时间仅与块长相关而无关块数，因此只要将块长缩短至(30)左右（受(f)数组空间限制）便可以通过啦。
AC代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define rg register
using namespace std;
const int N=1e5+10,S=4010;
int a[N],b[N],c[N],pos[N],tmp[N],l[S],r[S],f[S][S];
vector<int> num[N];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline int cal(int x,int u,int v)
{
if(!x) return 0;
return upper_bound(num[x].begin(),num[x].end(),v)-upper_bound(num[x].begin(),num[x].end(),u-1);
}
inline void updat(int &ma,int &id,int v,int i)
{
if(v>ma || (v==ma && c[i]<c[id])) ma=v,id=i;
}
inline int query(int x,int y)
{
int p=pos[x],q=pos[y],ma=0,id;
if(p==q)
{
for(rg int i=x;i<=y;i++) updat(ma,id,cal(c[i],x,y),i);
return a[id];
}
for(rg int i=x;i<=r[p];i++) updat(ma,id,cal(c[i],x,y),i);
updat(ma,id,cal(c[f[p+1][q-1]],x,y),f[p+1][q-1]);
for(rg int i=l[q];i<=y;i++) updat(ma,id,cal(c[i],x,y),i);
return a[id];
}
int main()
{
int n=read();
for(rg int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1); int m=unique(b+1,b+n+1)-b-1;
for(rg int i=1;i<=n;i++) {c[i]=lower_bound(b+1,b+m+1,a[i])-b; num[c[i]].push_back(i);}
int len=30,cnt=n/30;
for(rg int i=1;i<=cnt;i++) l[i]=(i-1)*len+1,r[i]=i*len;
if(r[cnt]<n) l[cnt+1]=r[cnt]+1,r[++cnt]=n;
for(rg int i=1;i<=cnt;i++)
{
memset(tmp,0,sizeof(tmp));
for(rg int j=l[i];j<=r[i];j++) pos[j]=i;
int ma=0,id;
for(rg int j=i;j<=cnt;j++)
{
for(rg int k=l[j];k<=r[j];k++)
{
tmp[c[k]]++;
if(tmp[c[k]]>ma || (tmp[c[k]]==ma && c[k]<c[id])) ma=tmp[c[k]],id=k;
}
f[i][j]=id;
}
}
while(n--)
{
int x=read(),y=read();
printf("%d
",query(x,y));
}
return 0;
}