题目大意：给一个数列，每次询问一个区间内有没有一个数出现次数超过一半

输入输出样例
输入 #1复制
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
输出 #1复制
1
0
3
0
4

就是很明显的主席树，我们每次查询时，看左右区间的和*2 是否大于当前我们查询的区间长度即可。

如果不满足，返回0；

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int n,q,root[N],cnt,x;
struct node{
	int l,r,sum;
}t[N<<5];
void change(int l,int r,int &x,int y,int k){
	x=++cnt; t[x]=t[y]; t[x].sum++;
	if(l==r)	return ; int mid=l+r>>1;
	if(k<=mid)	change(l,mid,t[x].l,t[y].l,k);
	else	change(mid+1,r,t[x].r,t[y].r,k);
}
int ask(int l,int r,int x,int y,int k){
	if(l==r)	return l;	int mid=l+r>>1;
	if(2*(t[t[y].l].sum-t[t[x].l].sum)>k)	return ask(l,mid,t[x].l,t[y].l,k);
	if(2*(t[t[y].r].sum-t[t[x].r].sum)>k)	return ask(mid+1,r,t[x].r,t[y].r,k);
	return 0;
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)	scanf("%d",&x),change(1,n,root[i],root[i-1],x);
	while(q--){
		int l,r; scanf("%d %d",&l,&r); 
		printf("%d\n",ask(1,n,root[l-1],root[r],r-l+1));
	}
	return 0;
}