区间内最频繁元素查询（Range Minimum Query 变种） 题目描述 给定一个整数数组，你需要处理多组查询。每组查询给出一个区间 [ L, R]，要求你快速找出该区间内出现次数最多的元素的出现次数（即频率最大值）。例如，数组为 [ 1, 3, 3, 5, 5, 5, 7]，查询 [ 1, 5]（0-based 索引）对应子数组 [ 3, 3, 5, 5, 5 ]，其中元素 5 出现 3 次，频率最大，因此答案为 3。 解题思路 这个问题是 Range Minimum Query（RMQ）的变种，但目标不是最小值而是最大频率。直接遍历每个查询的代价是 O(n) 每查询，当查询很多时会很慢。我们需要利用数组的特性设计高效方法。 关键观察 如果数组是 有序 的，相同元素会连续出现（但题目未排序）。不过，我们可以将数组分段，使相同元素尽量连续处理。常用方法是基于"块"的分解或线段树，但这里介绍一种利用"众数"性质的方法： 预处理相同元素的位置 ：记录每个值出现的所有索引。 分段处理 ：如果查询区间恰好覆盖某个值的完整连续段，可以快速计算频率；但更一般的方法是使用 莫队算法 （Mo's Algorithm），它通过调整查询顺序来优化。 步骤讲解 步骤 1：问题分析 直接扫描每个查询区间需要 O(n) 时间，m 个查询需要 O(mn)，在 n 和 m 较大时（如 >10^5）不可行。 需要预处理数据，使每个查询能在亚线性时间内完成。 步骤 2：莫队算法思想 将查询离线（先全部收集），然后按特定顺序重新排列。 将数组分成 √n 大小的块。将每个查询按 L 所属的块分组，同组内按 R 排序。 维护当前区间 [ l, r ] 的频率统计（使用哈希表），通过移动 l 和 r 来调整到新查询区间。由于排序后移动次数减少，总复杂度降至 O((n+m)√n)。 步骤 3：详细步骤 分块 ：设 block_ size = √n，计算每个索引 i 所属块号 block_ i = i / block_ size。 排序查询 ：对每个查询 [ L, R ]，先按 L 的块号升序排列，同块内按 R 升序（奇偶块可优化：奇数块 R 升序，偶数块降序，减少移动）。 初始化 ：设当前 l=0, r=-1（空区间），哈希表 freq 记录每个值的出现次数，变量 max_ freq 记录当前最大频率。 处理每个查询 ： 通过移动 l 和 r 来扩展到目标区间 [ L, R ]。 移动时更新 freq 和 max_ freq：当增加元素时，增加其频率并更新 max_ freq；当移除元素时，减少其频率，如果该元素频率原为 max_ freq 且减少后不再有元素达到该值，则 max_ freq 减 1（需检查，但为简化可暂存所有频率值或用频率的频率数组优化）。 记录答案 ：当前 max_ freq 即为该查询结果。 步骤 4：复杂度分析 L 移动：每个查询块内最多移动 O(√n)，总 O(m√n)。 R 移动：同块内 R 递增，总 O(n√n)。 总复杂度 O((n+m)√n)，适用于 n, m ≤ 10^5。 举例说明 数组: [ 1, 3, 3, 5, 5, 5, 7], n=7, block_ size≈2。 查询: [ 1,5]（索引从 0 开始，即子数组 [ 3,3,5,5,5 ]）。 处理： 排序后查询顺序不变（仅一个查询）。 从 [ 0,-1] 开始，扩展 r 到 5，依次添加元素：添加索引 0 值 1（freq[ 1]=1, max_ freq=1），索引 1 值 3（freq[ 3]=1），索引 2 值 3（freq[ 3]=2, max_ freq=2），索引 3 值 5（freq[ 5]=1），索引 4 值 5（freq[ 5]=2），索引 5 值 5（freq[ 5]=3, max_ freq=3）。 此时 l=0 但 L=1，需移动 l 到 1：移除索引 0 值 1（freq[ 1]=0, max_ freq 仍为 3）。 得查询 [ 1,5] 结果 max_ freq=3。 通过这种方法，我们可以高效处理大量区间查询。