记录编号	140954	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2014] 快递员	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	6.071 s
提交时间	2014-11-27 07:47:03	内存使用	7.94 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=500010;
int random(int x,int y){return rand()%(y-x+1)+x;}
int N,M;
vector<int> C[SIZEN];//每个快递公司接收包裹的时间
int P[SIZEN];
inline int calc(int k,int l,int r){//k公司在l~r时间送了多少个包裹
	return upper_bound(C[k].begin(),C[k].end(),r)-lower_bound(C[k].begin(),C[k].end(),l);
}
void determine(void){
	int l,r;
	scanf("%d%d",&l,&r);
	static int tim=20;
	int len=r-l+1;
	for(int i=1;i<=tim;i++){
		int a=P[random(l,r)];
		if(calc(a,l,r)*2>len){
			printf("%d\n",a);
			return;
		}
	}
	printf("0\n");
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++){
		scanf("%d",&P[i]);
		C[P[i]].push_back(i);
	}
}
int main(){
	freopen("kur.in","r",stdin);
	freopen("kur.out","w",stdout);
	srand(998);
	read();
	for(int i=1;i<=M;i++) determine();
	return 0;
}