题解

题目类型：可持久化线段树（主席树）
核心任务：多次区间查询某个“出现次数超过一半”的元素（即区间众数判定）。

---

一、题意概述

给定一个长度为 ( n ) 的数列 ( a_1, a_2, \dots, a_n )，以及 ( m ) 次查询，每次给出一段区间 ([l,r])。
对于每个查询，需要判断该区间内是否存在某个数出现次数超过一半（即 ( >\frac{r-l+1}{2} )），
若存在，则输出该数；若不存在，则输出 0。

---

二、算法思路：可持久化线段树（主席树）

1️⃣ 可持久化线段树的作用

主席树是一种 记录前缀信息的持久化数据结构，可在 (O(\log n)) 时间内实现如下操作：

• 快速查询区间 ([l,r]) 中某个数值出现次数；
• 通过根节点差 rt[r] - rt[l-1] 获取“差分区间”数据；
• 每个节点仅在插入时新建一小部分（log 层），总复杂度 (O(n \log n))。

在本题中，我们将值域设为 ([1,n])，每个位置 i 插入一个值 a[i]，维护前缀出现次数。

---

2️⃣ 主席树节点定义

struct tree {
	int ls, rs;  // 左右子节点编号
	int cnt;     // 当前区间内的计数
} tr[N * 20];

• 每个版本的根节点编号保存在 rt[i] 中；
• rt[i] 表示序列前缀 [1, i] 的统计信息；
• new_node() 用于复制上一版本节点（持久化核心）；
• modify() 用于在对应值 x 上 +1，构建新的版本。

---

3️⃣ 构建过程

for (int i = 1; i <= n; i++) {
    int x; scanf("%d", &x);
    rt[i] = rt[i - 1];   // 从上一个版本拷贝
    modify(rt[i], 1, n, x, 1); // 在位置 x 上出现一次
}

• 第 i 次插入得到第 i 个版本；
• 每个版本与前一版本仅有 (O(\log n)) 个新节点；
• 因此总空间复杂度 (O(n \log n))。

---

4️⃣ 查询逻辑：查找是否存在“过半数元素”

函数：

int query(int id1, int id2, int l, int r, int k)

其中：

• id1 是前缀版本 rt[l-1]
• id2 是前缀版本 rt[r]
• 通过 (tr[id2].cnt - tr[id1].cnt) 获得区间 [l, r] 的频次

判断条件：

if ((tr[id2].cnt - tr[id1].cnt) * 2 <= k) return 0;

表示当前区间总频次不足半数（没有超过一半的候选），返回 0。

若当前节点为叶子（l == r），即找到了出现次数最多的候选值。

否则：

• 先查看左子树中该元素数量是否超过半数；
• 若是，则继续往左；
• 否则往右找。

int mid = (l + r) / 2;
int x = tr[tr[id2].ls].cnt - tr[tr[id1].ls].cnt;
if (x * 2 > k) return query(tr[id1].ls, tr[id2].ls, l, mid, k);
return query(tr[id1].rs, tr[id2].rs, mid + 1, r, k);

这就相当于在二分值域上查找出现次数超过一半的那个数。

---

三、算法正确性说明

• 主席树记录了从前缀 1～r 的出现频率；
• 差分 rt[r] - rt[l-1] 恰好代表区间 [l,r]；
• 查询时不断往下递归，判断左右区间内是否存在出现次数超过半数的值；
• 若出现次数都 ≤ 半数，则返回 0；
• 否则定位到该具体数值。

因此每次查询能在 (O(\log n)) 时间内得到答案。

---

四、复杂度分析

操作	复杂度
建树	(O(n \log n))
单次查询	(O(\log n))
总复杂度	(O((n+m)\log n))
空间复杂度	(O(n \log n))

---

五、代码解释关键点

if ((tr[id2].cnt - tr[id1].cnt) * 2 <= k)
    return 0;  // 当前区间无过半元素
if (l == r)
    return l;  // 找到候选数值

• k = r - l + 1：当前区间长度；
• 2 * cnt <= k：即 cnt ≤ floor(k/2)，没有过半数；
• 否则继续往下查找更具体的区间。

---

六、总结

• 技术要点：主席树的“版本差”思想；
• 核心判断：出现次数 ×2 是否超过区间长度；
• 应用场景：区间众数、区间多数元素、频率统计问题。

---

七、完整代码（与题目一致）

#include <bits/stdc++.h>
using namespace std;

namespace Cherry {
	const int N=5e5+5;
	int n,m,cnt;
	int rt[N];
	struct tree {
		int ls,rs,cnt;
	}tr[N*20];
	int new_node(int x) { return tr[++cnt]=tr[x],cnt; }
	void pushup(int id) { tr[id].cnt=tr[tr[id].ls].cnt+tr[tr[id].rs].cnt; }
	void modify(int &id,int l,int r,int x,int d) {
		id=new_node(id);
		if(l>=x&&r<=x) return tr[id].cnt+=d,void();
		int mid=(l+r)/2;
		if(x<=mid) modify(tr[id].ls,l,mid,x,d);
		else modify(tr[id].rs,mid+1,r,x,d);
		pushup(id);
	}
	int query(int id1,int id2,int l,int r,int k) {
		if((tr[id2].cnt-tr[id1].cnt)*2<=k) return 0;
		if(l==r) return l;
		int mid=(l+r)/2;
		int x=tr[tr[id2].ls].cnt-tr[tr[id1].ls].cnt;
		if(x*2>k) return query(tr[id1].ls,tr[id2].ls,l,mid,k);
		return query(tr[id1].rs,tr[id2].rs,mid+1,r,k);
	}
	int main() {
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) {
			int x;
			scanf("%d",&x);
			rt[i]=rt[i-1];
			modify(rt[i],1,n,x,1);
		}
		for(int i=1;i<=m;i++) {
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%d\n",query(rt[l-1],rt[r],1,n,r-l+1));
		}
		return 0;
	}
}

int main() {
	Cherry::main();
	return 0;
}