洛谷评测机真神奇

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
const int N=500010;
inline void read(int &x)
{
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
}
inline void write(int x)
{
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
int n,m;
int a[N];
int cnt[N];
int maxx,ch;
struct Q{
	int idx,l,r,ll,rr;
}q[N];
int len;
inline bool cmp(Q a1,Q a2)
{
	if(a1.ll!=a2.ll)
		return a1.ll<a2.ll;
	return a1.r<a2.r;
}
inline void add(int x)
{
	cnt[x]++;
	ch++;
	cnt[x]>(ch>>1)?maxx=x:1;
	cnt[maxx]<=(ch>>1)?maxx=0:1;
}
int ans[N];
int biao;
int l,r,ll;
int cmaxx,cch;
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("my.out","w",stdout);
	read(n),read(m);
	len=sqrt(n);
	for(int i=1;i<=n;i++)
		read(a[i]);
	for(int i=1;i<=m;i++)
		q[i].idx=i,read(q[i].l),read(q[i].r),q[i].ll=q[i].l/len+1,q[i].rr=q[i].r/len+1;
	sort(q+1,q+m+1,cmp);
	for(int k=1;k<=m;)
	{
		while(q[k].rr==q[k].ll)
		{
			for(int i=q[k].l;i<=q[k].r;i++)
				add(a[i]);
			ans[q[k].idx]=maxx;
			maxx=0,ch=0;
			for(int i=q[k].l;i<=q[k].r;i++)
				cnt[a[i]]--;
			k++;
		}
		biao=q[k].ll;
		ll=q[k].ll*len+1,r=ll-1;
		maxx=0,ch=0;
		while(q[k].ll==biao)
		{
			while(r<q[k].r)
				add(a[++r]);
			l=ll;
			cmaxx=maxx,cch=ch;
			while(l>q[k].l)
				add(a[--l]);
			ans[q[k].idx]=maxx;
			maxx=cmaxx,ch=cch;
			ll--;
			for(int i=q[k].l;i<=ll;i++)
				cnt[a[i]]--;
			ll++;
			k++;
		}
		maxx=0,ch=0;
		for(int i=ll;i<=r;i++)
			cnt[a[i]]--;
	}
	for(int i=1;i<=m;i++)
		write(ans[i]),putchar(10);
	return 0;
}