RT

TLE65(53,55-64)

#include<bits/stdc++.h>
using namespace std;

int n,m,a[500001],lsh[500001],p,c[500001],cnt[1001][1001],cnt1[1001][1001],b[500001];
vector<int>v[500001];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],lsh[i]=a[i];
	p=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		b[i]=v[a[i]].size();
		v[a[i]].push_back(i);
	}
	int ia=0;
	for(int i=1;i<=n;i+=p)
	{
        if(i==p*ia+1)ia++;
		int ja=ia;
		for(int j=i;j<=n;j++)
		{
		    if(j==p*ja+1)ja++;
			if(cnt[ia][ja]<cnt[ia][ja])cnt1[ia][ja]=cnt1[ia][ja];
			cnt[ia][ja]=max(cnt[ia][ja],cnt[ia][ja]);
			if(cnt[ia][ja]==cnt[ia][ja])cnt1[ia][ja]=min(cnt1[ia][ja],cnt1[ia][ja-1]);
			c[a[j]]++;
			if(cnt[ia][ja]<c[a[j]])cnt1[ia][ja]=a[j];
			cnt[ia][ja]=max(c[a[j]],cnt[ia][ja]);
			if(cnt[ia][ja]==c[a[j]])cnt1[ia][ja]=min(cnt1[ia][ja],a[j]);
		}
		for(int j=i;j<=n;j++)
		{	
			c[a[j]]=0;
		}
	}
	int ans=0,ans1=0;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		int la=(l-1)/p+1,ra=(r-1)/p+1;
		ans=cnt[la+1][ra-1];
		ans1=cnt1[la+1][ra-1];
		for(int j=l;j<=min(la*p,r);)
		{
			if(b[j]+ans-1<v[a[j]].size()&&v[a[j]][b[j]+ans-1]<=r)ans1=min(ans1,a[j]);
			if(b[j]+ans<v[a[j]].size()&&v[a[j]][b[j]+ans]<=r)
			{
				ans++;
				ans1=a[j];
			}
			else j++;
		}
		for(int j=r;j>=max(ra*p-p+1,l);)
		{
			if(b[j]-ans+1<v[a[j]].size()&&v[a[j]][b[j]-ans+1]>=l)ans1=min(ans1,a[j]);
			if(b[j]-ans<v[a[j]].size()&&v[a[j]][b[j]-ans]>=l)
			{
				ans++;
				ans1=a[j];
			}
			else j--;
		}
        if(ans<<1>r-l+1)cout<<ans1<<"\n";
        else cout<<"0\n";
	}
    return 0;
}