题意
给定序列，多次查询区间 $[l, r]$ 内出现次数严格大于 $\frac{r-l+1}{2}$ 的数。

关键性质
如果一个数在区间中出现次数超过一半，那么它一定是这个区间的绝对众数。

核心算法
使用可持久化线段树（主席树）：

• 对序列的每个前缀建立线段树，记录值域区间内数的个数
• 查询时通过两个前缀线段树的差值得到区间内每个数的出现次数
• 利用绝对众数的性质：如果存在绝对众数，那么在任意划分的区间中，它至少在一个子区间中也是众数

查询过程

1. 尝试在区间中找到可能的候选值（通过线段树递归）
2. 检查候选值在区间中的出现次数是否确实大于一半

时间复杂度

• 预处理：$O(n \log n)$
• 单次查询：$O(\log n)$
• 总复杂度：$O((n+m) \log n)$

代码要点

• 动态开点线段树
• 版本对应每个前缀
• 查询时同时检查两个儿子区间的数量差

标签
数据结构、树结构（主席树）