L3-002 特殊堆栈（树状数组+二分）

原题链接

堆栈作为一种典型的线性数据结构，其遵循后进先出的原则，主要的操作包括“入栈”（即将元素添加至堆栈顶部）以及“出栈”（即从堆栈顶部移除并返回该元素）。本题需要实现一种额外的操作：“取中值”，即返回当前堆栈内所有元素键值的中位数。当元素个数 N 为偶数时，中值定义为第 N/2 小的元素；若 N 为奇数，则中值为第 (N+1)/2 小的元素。

输入格式：
输入的第一行包含一个正整数 N（≤10
5
）。接下来的 N 行，每一行给出一个指令，共有三种类型：

Push key
Pop
PeekMedian

其中 key 是一个不超过 10
5
的正整数；Push 表示执行“入栈”操作；Pop 表示执行“出栈”操作；PeekMedian 表示执行“取中值”操作。

输出格式：
对于每一个 Push 操作，将对应的 key 插入到堆栈中，无需输出结果；对于每一个 Pop 或 PeekMedian 操作，在单独的一行中输出相应的返回结果。如果遇到非法操作，则输出 Invalid。

    17
    Pop
    PeekMedian
    Push 3
    P