17370845950

本文详解如何在大规模数据约束下（n, q ≤ 5×10⁴）快速响应多次子数组中位数查询，重点分析朴素排序法的局限性，并提供可落地的优化思路与正确实现。

在处理子数组中位数查询问题时，核心在于准确理解题设定义：子数组 A[L..R] 的中位数是将其元素升序排列后，位于位置 ⌈len/2⌉（1-indexed）的元素。例如子数组长度为 5，则中位数是第 3 个元素；长度为 4，则是第 2 个元素（非平均值！），即下取整意义上的“左中位数”。这一点极易被误读为偶数长度时取中间两数平均值——但题目明确说明：“ceil(len/2) is called the median”，因此 中位数恒为排序后索引 k = (len - 1) / 2（0-indexed）处的元素。

✅ 正确计算中位数索引（0-indexed）

设子数组长度 len = R - L + 1，则 1-indexed 中位位置为 pos = ⌈len/2⌉，对应 0-indexed 索引为：

int k = (len - 1) / 2; // 等价于 (int) Math.ceil(len / 2.0) - 1

例如：

• len=5 → k = (5-1)/2 = 2 → 第 3 个元素（0-indexed 下标 2）✅
• len=4 → k = (4-1)/2 = 1 → 第 2 个元素（0-indexed 下标 1）✅

⚠️ 注意：你提供的“尝试代码”中存在多处逻辑错误： median(int N, int[] A) 方法未使用参数 N 实际长度，却对整个 A 排序； getMedian() 递归截断逻辑（Arrays.copyOfRange(A, 1, mid+1)）与题目要求的 Q 次任意 [L,R] 查询完全无关； 示例输出 3, 4, 5 对应输入 {2,4,5,3,1,6} 并未说明查询区间，实际应为： Query1: [1,3] → {2,4,5} → sorted → {2,4,5} → median = 4？但示例输出首项是 3 → 实际应为 [1,5]: {2,4,5,3,1} → sorted {1,2,3,4,5} → median = 3； 因此示例隐含查询为 [1,5], [2,4], [3,6] 等，需严格按输入 L,R 提取子数组。

✅ 标准解法（适用于 Q ≤ 5×10⁴ 的务实方案）

由于 N, Q 同阶于 5×10⁴，对每个查询都 Arrays.sort(subarray) 的时间复杂度为 O(Q × len × log len)，最坏情况（如每次查整个数组）达 O(Q × N log N) ≈ 5e4 × 5e4 × log(5e4) ≈ 10¹⁰，Java 中必然超时。但若数据无极端卡点，且平均子数组较短，该方法仍可作为基准实现：

import java.util.*;

public class MedianQueries {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();

        int Q = sc.nextInt();
        while (Q-- > 0) {
            int L = sc.nextInt() - 1; // convert to 0-indexed
            int R = sc.nextInt() - 1;
            int len = R - L + 1;
            int[] sub = Arrays.copyOfRange(A, L, R + 1);
            Arrays.sort(sub);
            int k = (len - 1) / 2; // 0-indexed median position
            System.out.println(sub[k]);
        }
    }
}

? 进阶优化方向（应对严格时限）

若需真正通过 N, Q = 5×10⁴ 的极限数据，应转向以下技术之一：

• Mo's Algorithm + Balanced BST / Fenwick Tree：离线处理，按块排序查询，维护当前区间内元素频次，二分查找第 k 小值 —— 时间复杂度 O((N + Q) √N log A_max)；
• 整体二分 / 主席树（可持久化线段树）：支持在线查询任意区间第 k 小，预处理 O(N log A_max)，单次查询 O(log A_max)；
• 随机快速选择（QuickSelect）：对每个子数组调用 select(sub, k)，期望 O(len)，避免全排序，实践中常比 Arrays.sort() 更快。

✅ 总结

• 中位数定义以 ⌈len/2⌉（1-indexed）为准 → 对应 0-indexed 下标 (len-1)/2；
• 勿混淆“数学中位数”（偶数长取均值）与本题“竞赛定义中位数”（恒取左中位）；
• 初学推荐先实现朴素 sort + index 版本验证逻辑；
• 生产级或 OJ 高分需掌握 QuickSelect 或主席树等高级数据结构。

掌握此题，是深入理解区间查询、排序与选择算法边界的良好起点。