题目链接：https://loj.ac/problem/6285
其实一看到是离线，我就想用莫队算法来做，对所有询问进行分块，但是左右边界移动的时候，不会同时更新数字最多的数，只是后面线性的扫了一遍，所以还有百分之12的样例过不了。
然后看了别人分块，是先对所有零散的数字编号（这个应该是所谓离散化），用vector[i]存储编号为i的数字所有出现的位置，因为从0到n，所以里面的值是升序的，我们先对块与块之间数字最多的数进行计算（预处理），在查询的时候查询[l,r]之间的数，把区间分成三块，左边不完整的块，中间完整的块，后面不完整的块，对于不完整的块可以遍历每一个元素用二分查找相应编号的vector里面在这个范围的数字有多少，完整的块就直接把预处理的数字拿出来。我做这题超时无数次，建议就是尽量减少map的调用，在查找时对于找过的数字编号可以标记，下次不找，然后块的大小可以设成block=80，我做的时候就是因为map调用太多，块的大小一直是sqrt（n），然后一直超时。
代码比较丑：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100010
int a[maxn],num[maxn],MAX[][],lump[maxn],val[maxn];//num计数，MAX记录块与块之间最多的数字对应编号
// lump记录组，val保存原始值
vector<int>ve[maxn];
bool vis[maxn];//标记
map<int,int>mp;
int n,m,k,t,block,id;
void cal(int x)//预处理
{
int count1=,max1=;
memset(num,,sizeof(num));
for(int i=(x-)*block+;i<=n;i++)
{
int s=a[i];
num[s]++;
if(num[s]>count1||num[s]==count1&&val[s]<val[max1])
{
count1=num[s];
max1=s;
}
MAX[x][lump[i]]=max1;
}
}
int ask(int x,int l,int r)//二分查找
{
return upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);
}
int find(int l,int r)
{
memset(vis,,sizeof(vis));
int ans=,count1=;
ans=MAX[lump[l]+][lump[r]-];
count1=ask(ans,l,r);
vis[ans]=true;//记录编号为ans的数字查找过
for(int i=l;i<=min(lump[l]*block,r);i++)
{
if(vis[a[i]])
continue;
vis[a[i]]=true;
int count2=ask(a[i],l,r);
if(count2>count1||count1==count2&&val[a[i]]<val[ans])
{
count1=count2;
ans=a[i];
}
}
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*block+;i<=r;i++)
{
if(vis[a[i]])
continue;
vis[a[i]]=true;
int count2=ask(a[i],l,r);
if(count2>count1||count1==count2&&val[a[i]]<val[ans])
{
count1=count2;
ans=a[i];
}
}
}
return val[ans];
}
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int main()
{
scanf("%d",&n);
block=;//这里很多人都写了80，。。。。。。
id=;
for(int i=;i<=n;i++)
{
a[i]=read();
lump[i]=(i-)/block+;
if(mp[a[i]]==)
{
mp[a[i]]=++id;
val[id]=a[i];//保存原始值
}
a[i]=mp[a[i]];//这个是保存编号，减少map调用，之前我没有这个一直超时
ve[a[i]].push_back(i);
}
for(int i=;i<=lump[n];i++)
cal(i);
int l,r;
for(int j=;j<=n;j++)
{
l=read();
r=read();
printf("%d\n",find(l,r));
}
return ;
}