记录编号	454958	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2014] 快递员	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.855 s
提交时间	2017-09-30 17:25:25	内存使用	71.14 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
int n,m;
int a[500005];
int cnt;
int rt[500005],lch[10000005],rch[10000005],sum[10000005];
inline void update(int &x,int las,int pos,int l,int r){
	x=++cnt;
	lch[x]=lch[las];
	rch[x]=rch[las];
	sum[x]=sum[las]+1;
	if(l==r)
		return;
	int mid((l+r)>>1);
	if(pos<=mid)
		update(lch[x],lch[las],pos,l,mid);
	else
		update(rch[x],rch[las],pos,mid+1,r);
}
inline int query(int x,int y,int l,int r,int k){
	if(l==r){
		if(sum[y]-sum[x]>k)
			return l;
		return 0;
	}
	int mid((l+r)>>1);
	if(sum[lch[y]]-sum[lch[x]]>k)
		return query(lch[x],lch[y],l,mid,k);
	if(sum[rch[y]]-sum[rch[x]]>k)
		return query(rch[x],rch[y],mid+1,r,k);
	return 0;
}
inline int gg(){
	freopen("kur.in","r",stdin);
	freopen("kur.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		update(rt[i],rt[i-1],a[i],1,n);
	}
	while(m--){
		int x(read()),y(read());
		printf("%d\n",query(rt[x-1],rt[y],1,n,(y-x+1)>>1));
	}
	return 0;
}
int K(gg());
int main(){;}