#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 常量定义：最大节点数和版本数
const int MAXN = 5e4 + 5;  

// 线段树节点结构体
struct Node {
    int l, r;    // 左右子节点指针（数组下标）
    int cnt;     // 当前区间元素计数
} tree[MAXN * 20];  // 预估节点数（n*logn）

int root[MAXN];  // 各版本根节点指针
int cnt;         // 动态开点计数器
vector<int> nums;// 离散化数组

// 构建初始空树
void build(int &node, int l, int r) {
    node = ++cnt;  // 分配新节点
    if(l == r) return;  // 叶子节点直接返回
    int mid = (l + r) >> 1;
    build(tree[node].l, l, mid);   // 递归构建左子树
    build(tree[node].r, mid+1, r); // 递归构建右子树
}

// 更新操作（创建新版本）
void update(int pre, int &cur, int l, int r, int pos) {
    cur = ++cnt;            // 分配新节点
    tree[cur] = tree[pre];  // 复制前驱节点信息
    tree[cur].cnt++;        // 计数+1
    if(l == r) return;      // 到达叶子节点
    int mid = (l + r) >> 1;
    // 根据插入位置选择更新左/右子树
    if(pos <= mid) update(tree[pre].l, tree[cur].l, l, mid, pos);
    else update(tree[pre].r, tree[cur].r, mid+1, r, pos);
}

// 查询区间第k小（用于找候选众数）
int query(int u, int v, int l, int r, int k) {
    if(l == r) return l;  // 找到目标位置
    int mid = (l + r) >> 1;
    // 计算左子树元素个数差
    int left_cnt = tree[tree[v].l].cnt - tree[tree[u].l].cnt;
    // 根据数量决定查询方向
    if(left_cnt >= k) 
        return query(tree[u].l, tree[v].l, l, mid, k);
    else 
        return query(tree[u].r, tree[v].r, mid+1, r, k - left_cnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  // 加速IO
    
    int n, m;
    cin >> n >> m;
    vector<int> c(n+1);  // 原始数据（1-based）
    
    // 离散化处理
    for(int i = 1; i <= n; ++i) {
        cin >> c[i];
        nums.push_back(c[i]);
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    int sz = nums.size();  // 离散化后值域大小
    
    // 初始化主席树
    build(root[0], 1, sz);  // 第0版本（空树）
    
    // 逐个插入元素创建新版本
    for(int i = 1; i <= n; ++i) {
        // 计算离散化后的位置（1-based）
        int pos = lower_bound(nums.begin(), nums.end(), c[i]) - nums.begin() + 1;
        update(root[i-1], root[i], 1, sz, pos);
    }
    
    // 处理查询
    while(m--) {
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;
        // 查询中位数位置作为候选（众数必定是中位数候选）
        int candidate_pos = query(root[l-1], root[r], 1, sz, (len+1)/2);
        int candidate = nums[candidate_pos - 1];  // 转回原始值
        
        // 验证候选是否真实过半
        auto lb = lower_bound(c.begin()+l, c.begin()+r+1, candidate);
        auto ub = upper_bound(c.begin()+l, c.begin()+r+1, candidate);
        int cnt = ub - lb;  // 实际出现次数
        
        // 输出结果（过半输出值，否则输出0）
        cout << (cnt > len/2 ? candidate : 0) << '\n';
    }
    return 0;
}


代码说明：这段代码实现了基于主席树的区间众数查询系统，通过离散化+可持久化线段树高效处理区间统计问题。核心思想是通过维护历史版本实现区间查询，空间复杂度O(nlogn)，查询时间复杂度O(logn)。