LOJ纪录

非照搬，输入有改动

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define endl "\n"
using namespace std;
const int N=1e5+5;
const int INF=1e9;
const double EPS=1e-6;
const int MOD=998244353;
int n,k,a[N],b[N],s[1005][1005],pre[405][N],c[N],m;
void solve(){
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i],b[i]=a[i];
	sort(b,b+n);
	int cnt=unique(b,b+n)-b;
	for(int i=0;i<n;i++)a[i]=lower_bound(b,b+cnt,a[i])-b;
	k=sqrt(n);
	for(int i=0;i<(n-1)/k+1;i++){
		memset(c,0,sizeof c);
		int sum=0,ans=0;
		for(int j=i*k;j<n;j++){
			c[a[j]]++;
			if(c[a[j]]>sum||c[a[j]]==sum&&a[j]<ans)sum=c[a[j]],ans=a[j];
			if((j+1)%k==0||j+1==n)s[i][j/k]=ans;
		}
	}
	memset(c,0,sizeof c);
	for(int i=0;i<n;i++){
		for(int j=i/k;j<(n-1)/k+1;j++){
			pre[j][a[i]]++;
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		l--,r--;
		int ans=0,sum=0;
		if(l/k==r/k){
			for(int i=l;i<=r;i++){
				c[a[i]]++;
				if(c[a[i]]>sum||c[a[i]]==sum&&a[i]<ans)sum=c[a[i]],ans=a[i];
			}
			for(int i=l;i<=r;i++)c[a[i]]=0;
		}else{
			for(int i=l;i<(l/k+1)*k;i++){
				c[a[i]]++;
				int x=pre[r/k-1][a[i]]-pre[l/k][a[i]]+c[a[i]];
				if(x>sum||x==sum&&a[i]<ans)sum=x,ans=a[i];
			}
			for(int i=r/k*k;i<=r;i++){
				c[a[i]]++;
				int x=pre[r/k-1][a[i]]-pre[l/k][a[i]]+c[a[i]];
				if(x>sum||x==sum&&a[i]<ans)sum=x,ans=a[i];
			} 
			if(r/k-l/k>1){
				int f=s[l/k+1][r/k-1],x=pre[r/k-1][f]-pre[l/k][f];
				if(x>sum||x==sum&&f<ans)sum=x,ans=f;
			}
			for(int i=l;i<(l/k+1)*k;i++)c[a[i]]=0;
			for(int i=r/k*k;i<=r;i++)c[a[i]]=0;
		}
		cout<<b[ans]<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    int T=1;
//	cin>>T;
    while(T--)solve();
    return 0;
}