#include<bits/stdc++.h>
//#define int long long
using namespace std;
int read(){
	int x=0,f=1;
	char c;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int N=5e5+1;
int n,q,a[N],b[N],m;
struct tree{
	int ls,rs,sum,jl;
}t[N*15+479055]; 		//二分空间30多次的结果
int rt[N];
int top;
int clone(int k){
	t[++top]=t[k];
	t[top].sum++;
	return top;
}
int upd(int k,int l,int r,int x){
	k=clone(k);
	if(l==r)return k;
	int mid=l+r>>1;
	if(mid>=x)t[k].ls=upd(t[k].ls,l,mid,x);
	else t[k].rs=upd(t[k].rs,mid+1,r,x);
	return k;
}
int qry(int L,int R,int l,int r,int len){
	if(l==r)return l;
	int ls=t[t[R].ls].sum-t[t[L].ls].sum,rs=t[t[R].rs].sum-t[t[L].rs].sum,mid=l+r>>1;
	if(ls>=len)return qry(t[L].ls,t[R].ls,l,mid,len);
	else if(rs>=len) return qry(t[L].rs,t[R].rs,mid+1,r,len);
	return 0;
}
signed main(){
	n=read(),q=read();
	for(int i=1;i<=n;i++)b[i]=a[i]=read();
	sort(b+1,b+1+n);
	m=unique(b+1,b+1+n)-1-b;
	for(int i=1;i<=n;i++){
		int t=lower_bound(b+1,b+1+m,a[i])-b;
		rt[i]=upd(rt[i-1],1,m,t);
	}
	while(q--){
		int l=read(),r=read();
		printf("%d\n",b[qry(rt[l-1],rt[r],1,m,(r-l+1)/2+1)]);
	}
	return 0;
}

不加离散化还挂的更多。

是这种主席树写法空间大吗？