题目链接：https://www.luogu.com.cn/problem/P1168

题解：动态维护前奇数项的中位数

题目大意

给定一个长度为 N 的非负整数序列 A ，要求对每个前缀 A_1, A_2, ，，A_{2i-1} （即前 1 项、前 3 项、前 5 项……）求出其中位数，并输出。

解题思路

中位数定义回顾

对于一个奇数长度的有序序列，中位数是排序后位于中间位置的那个数。

例如：[1,3,5] 的中位数是 3；[1,3,5,6,9] 的中位数是 5。

因此，对于前 2i - 1 个元素，我们要找出第 i 小的数。

暴力做法（不可行）

每次读入新元素后，对当前前缀排序并取中间值。

时间复杂度为 O(N^2 *log N)，在 N = 10^5 时会超时。

优化思路：双堆法（对顶堆）

我们可以使用 最大堆 + 最小堆 的结构来动态维护中位数：

• 最大堆 maxQ：保存较小的一半元素，堆顶是这部分的最大值。
• 最小堆 minQ：保存较大的一半元素，堆顶是这部分的最小值。

我们始终维护：

• 当处理到第 2i - 1 个元素时，maxQ 中恰好有 i 个元素；
• 此时 maxQ.top() 就是当前前缀的中位数。

插入与平衡策略

1. 插入新元素：如果 minQ 非空且当前值大于 minQ.top()，说明它属于较大一半，放入 minQ；否则放入 maxQ。
2. 奇数位置时调整堆大小：确保 maxQ.size() == (i + 1) / 2；若 maxQ 元素太少，从 minQ 转移堆顶；若 maxQ 元素太多，将堆顶移到 minQ。

这样，每次只需 O(log N) 时间插入和调整，总复杂度为 O(N log N)，可以轻松通过所有数据。

代码解析

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

int n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int val;
    // maxQ: 存放较小的一半，堆顶为最大值
    priority_queue<int> maxQ;
    // minQ: 存放较大的一半，堆顶为最小值
    priority_queue<int, vector<int>, greater<int>> minQ;

    for (int i = 1; i <= n; i++)
    {
        cin >> val;
        // 插入新元素
        if (!minQ.empty() && val > minQ.top())
            minQ.push(val);
        else
            maxQ.push(val);

        // 只有在奇数位置才需要输出中位数
        if (i & 1)
        {
            // 调整堆大小，使 maxQ 的大小为 (i+1)/2
            while (maxQ.size() < (i + 1) / 2)
            {
                maxQ.push(minQ.top());
                minQ.pop();
            }
            while (maxQ.size() > (i + 1) / 2)
            {
                minQ.push(maxQ.top());
                maxQ.pop();
            }
            // maxQ 的堆顶即为中位数
            cout << maxQ.top() << '\n';
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N log N)，每个元素最多入堆、出堆一次；
• 空间复杂度：O(N)，两个堆总共存储 N 个元素。

本题考察的是在线维护动态中位数的能力，使用对顶堆（双堆） 是经典高效的做法。掌握该技巧可解决大量涉及中位数、第 k 小元素等动态查询问题。