题目链接：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[2010][2010],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=0,max1=0; memset(num,0,sizeof(num)); for(int i=(x-1)*block+1;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,0,sizeof(vis)); int ans=0,count1=0; ans=MAX[lump[l]+1][lump[r]-1]; 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]-1)*block+1;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=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { scanf("%d",&n); block=80;//这里很多人都写了80，。。。。。。 id=0; for(int i=1;i<=n;i++) { a[i]=read(); lump[i]=(i-1)/block+1; if(mp[a[i]]==0) { mp[a[i]]=++id; val[id]=a[i];//保存原始值 } a[i]=mp[a[i]];//这个是保存编号，减少map调用，之前我没有这个一直超时 ve[a[i]].push_back(i); } for(int i=1;i<=lump[n];i++) cal(i); int l,r; for(int j=1;j<=n;j++) { l=read(); r=read(); printf("%d ",find(l,r)); } return 0; }