我的思路就是先求出这个区间的中位数，然后再求这个中位数的出现次数，如果出现次数大于n/2的话输出这个数，否则输出0

#include<bits/stdc++.h>
using namespace std;
const int maxm=5e5+10;
struct Persistent_Segment_Tree{
     int lch[maxm*21],rch[maxm*21],tot;
     int sum[maxm*21];
     inline void init(){
        tot=0;
     }
     inline void build(int &root,int L,int R){
         root=++tot;
          if(L==R){
            return;
          }
          int mid=(L+R)>>1;
          build(lch[root],L,mid);
          build(rch[root],mid+1,R);
     }
     inline void Copy(int from,int to){
           lch[to]=lch[from];
           rch[to]=rch[from];
           sum[to]=sum[from];
     }
     inline void update(int &root,int old,int cl,int cr,int l,int r,int x){
          root=++tot;
          Copy(old,root);
          sum[root]+=x*(r-l+1);
          if(l==cl&&r==cr) return;
          int mid=(cl+cr)>>1;
          if(r<=mid) update(lch[root],lch[root],cl,mid,l,r,x);
          else update(rch[root],rch[root],mid+1,cr,l,r,x);
     }
     inline int query(int s,int t,int L,int R,int k){
        if(L==R) return L;
        int mid=(L+R)>>1;
        if(k<=sum[lch[t]]-sum[lch[s]]){
            return query(lch[s],lch[t],L,mid,k);
        }
        else{
            return query(rch[s],rch[t],mid+1,R,k-(sum[lch[t]]-sum[lch[s]]));
        }
     }
     inline int qsum(int s,int t,int L,int R,int x){
            if(L==R) return sum[t]-sum[s];
            int mid=(L+R)>>1;
            if(x<=mid) return qsum(lch[s],lch[t],L,mid,x);
            else return qsum(rch[s],rch[t],mid+1,R,x);
     }//查询区间[s,t]中数字x出现的次数
     //求区间第k小
     //s和t反应的是根节点的位置(相当于一个)
     //L,R为当前s、t代表的区间端点值
};
Persistent_Segment_Tree seg;
int n,m;
int root[maxm];
int main(){
    scanf("%d%d",&n,&m);
    seg.init();
    seg.build(root[0],1,n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        seg.update(root[i],root[i-1],1,n,x,x,1);
    }
    while(m--){
        int L,R,k;
        scanf("%d%d",&L,&R);k=(R-L+1)/2+1;
        int num=seg.query(root[L-1],root[R],1,n,k);
        int cnt=seg.qsum(root[L-1],root[R],1,n,num);
        if(cnt>=k) printf("%d\n",num);
        else printf("0\n");
    }
    return 0;
}