题意简述

求区间严格大于区间长度一半的众数，若不存在则输出0。

这不就主席树模板题嘛

题目分析

求区间众数，其实可以很容易想到主席树（即可持久化权值线段树，不会的可以先去看看模板题P3834）。这里稍微讲一下主席树的基本思想，从左到右每插入一个数 $a_i$ 就产生一个版本的权值线段树 $T_i$ ，权值线段树每个节点上记录一个值 $sum$ ，表示该节点对应值域 $[L,R]$ 一共插入过多少数，即在此版本的权值线段树 $T_i$ 中值域区间 $[L,R]$ 里有多少个数。处理完所有数后，用类似前缀和的操作将 $TR$ 的 $sum$ 减去 $T{L-1}$ 的 $sum$ ，即可求出值域区间 $[L,R]$ 的数的个数。

基于以上主席树处理区间第 k 小问题的基本思想，我们已经能求出任意区间的数的个数，但题目要求的是区间严格大于区间长度一半的众数，这要怎么做呢？

其实很简单，对于一个权值线段树的节点，如果左儿子的数的个数比总数一半大，那么满足条件的众数就可能在左儿子里（也可能没有），此时再递归找左儿子，右儿子也同理。如果左右儿子的数的个数都比总数一半小，那显然左右儿子都不存在满足条件的众数。

要注意一点，当一个节点的左儿子满足条件时，众数不一定在左儿子里，右儿子也可能满足条件，所以两边都要判断和递归查找。

主席树更新和查找的时间复杂度都为 $O(n\log n)$ ，总时间复杂度为 $O((n+m)\log n)$ 。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50005;
int n,m,cnt,len,ans;

struct node{
    int ls,rs,sum,zl;
}tree[maxn<<5];
int c[maxn],root[maxn];

//建树
int build(int l,int r){
    int p=++cnt;
    if(l==r){
        tree[p].zl=1;
        return p;
    }
    int mid=(l+r)>>1;
    build(l,mid);
    build(mid+1,r);

    return p;
}

//插入操作
int update(int l,int r,int now,int val){
    int p=++cnt;
    tree[p]=tree[now];
    tree[p].sum++;

    if(l==r)return p;

    int mid=(l+r)>>1;

    if(val<=mid)tree[p].ls=update(l,mid,tree[p].ls,val);
    else tree[p].rs=update(mid+1,r,tree[p].rs,val);

    return p;
}

//询问
void query(int l,int r,int p,int q,int k){
    if(l==r){
        ans=l;
        return;
    }

    int m=(l+r)>>1;

    int lx=tree[tree[p].ls].sum-tree[tree[q].ls].sum;   //值域[l,m]上数的个数
    int rx=tree[tree[p].rs].sum-tree[tree[q].rs].sum;   //值域[m+1,r]上数的个数

    if(lx<=k and rx<=k){    //如果左右儿子的数的个数都比总数一半小，说明该区间上不存在
        ans=0;
        return;
    }

    if(lx>k)query(l,m,tree[p].ls,tree[q].ls,k);     //值域[l,m]上数的个数大于总数一半，就尝试在左边找

    if(rx>k)query(m+1,r,tree[p].rs,tree[q].rs,k);   //值域[m+1,r]上数的个数大于总数一半，就尝试在右边找
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>c[i],len=max(len,c[i]);

    root[0]=build(1,len);

    for(int i=1;i<=n;i++)root[i]=update(1,len,root[i-1],c[i]);

    while(m--){
        int l,r,k;
        cin>>l>>r;
        k=(r-l+1)>>1;
        query(1,len,root[r],root[l-1],k);
        cout<<ans<<endl;
    }

    return 0;
}