LG#P3871. [TJOI2010] 中位数

[TJOI2010] 中位数

P3871 [TJOI2010] 中位数

题目描述

\hspace{15pt}给定一个由 nn 个整数构成的序列,你需要支持以下两种操作:

1. {\hspace{20pt}}_\texttt{1.}\,在序列末尾添加一个整数 aa,序列长度增加 11;

2. {\hspace{20pt}}_\texttt{2.}\,输出当前序列的中位数。

\hspace{15pt}在本题中,中位数的定义如下:将序列中的数从小到大排列后,若序列长度为奇数,取正中间的那个数;若序列长度为偶数,取正中间两个数中较小的那个。

\hspace{15pt}例如:

∙ \hspace{23pt}\bullet\,序列 {1,2,13,14,15,16}\{1, 2, 13, 14, 15, 16\} 的中位数为 1313;

∙ \hspace{23pt}\bullet\,序列 {1,3,5,7,10,11,17}\{1, 3, 5, 7, 10, 11, 17\} 的中位数为 77;

∙ \hspace{23pt}\bullet\,序列 {1,1,1,2,3}\{1, 1, 1, 2, 3\} 的中位数为 11。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表序列的初始长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(-10^9 \leqq a_i \leqq 10^9\right)$ 代表初始序列。

\hspace{15pt}第三行输入一个整数 m(0≦m≦104)m \left(0 \leqq m \leqq 10^4\right) 代表操作次数。

\hspace{15pt}此后 mm 行,第 ii 行输入一条操作,格式为以下两种之一:

∙ add a\hspace{23pt}\bullet\,\texttt{add } a:在序列末尾添加整数 a(−109≦a≦109)a \left(-10^9 \leqq a \leqq 10^9\right);

∙ mid\hspace{23pt}\bullet\,\texttt{mid}:输出当前序列的中位数。

输出格式

\hspace{15pt}对于每次 mid\texttt{mid} 操作,新起一行输出一个整数代表当时序列的中位数。所有答案按操作的先后顺序输出。

测试样例

6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid
5
13

样例 1 解释

\hspace{15pt}初始序列为 {1,2,13,14,15,16}\{1, 2, 13, 14, 15, 16\}。前两次操作依次添加 55 和 33,序列变为 {1,2,13,14,15,16,5,3}\{1, 2, 13, 14, 15, 16, 5, 3\},从小到大排列为 {1,2,3,5,13,14,15,16}\{1, 2, 3, 5, 13, 14, 15, 16\}。此时长度为 88,正中间两个数为 55 和 1313,取较小的 55,因此第一次输出 55。

\hspace{15pt}随后添加 2020,序列长度为 99,从小到大排列为 {1,2,3,5,13,14,15,16,20}\{1, 2, 3, 5, 13, 14, 15, 16, 20\},正中间的数为 1313,因此第二次输出 1313。

5
7 1 4 9 2
5
add 6
mid
add 0
add -3
mid
4
2

样例 2 解释

\hspace{15pt}初始序列为 {7,1,4,9,2}\{7, 1, 4, 9, 2\}。添加 66 后长度为 66,从小到大排列为 {1,2,4,6,7,9}\{1, 2, 4, 6, 7, 9\},正中间两个数为 44 和 66,取较小的 44,因此第一次输出 44。

\hspace{15pt}随后依次添加 00 和 −3-3,长度为 88,从小到大排列为 {−3,0,1,2,4,6,7,9}\{-3, 0, 1, 2, 4, 6, 7, 9\},正中间两个数为 22 和 44,取较小的 22,因此第二次输出 22。

提示

\hspace{15pt}对于 30%30\% 的数据,1≦n≦1041 \leqq n \leqq 10^4,0≦m≦1030 \leqq m \leqq 10^3;对于 100%100\% 的数据,1≦n≦1051 \leqq n \leqq 10^5,0≦m≦1040 \leqq m \leqq 10^4。

\hspace{15pt}序列中的整数绝对值不超过 10910^9,且可能有重复。