P3871 [TJOI2010] 中位数
题目描述
给定一个由 n 个整数构成的序列,你需要支持以下两种操作:
1.在序列末尾添加一个整数 a,序列长度增加 1;
2.输出当前序列的中位数。
在本题中,中位数的定义如下:将序列中的数从小到大排列后,若序列长度为奇数,取正中间的那个数;若序列长度为偶数,取正中间两个数中较小的那个。
例如:
∙序列 {1,2,13,14,15,16} 的中位数为 13;
∙序列 {1,3,5,7,10,11,17} 的中位数为 7;
∙序列 {1,1,1,2,3} 的中位数为 1。
输入格式
第一行输入一个整数 n(1≦n≦105) 代表序列的初始长度。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-10^9 \leqq a_i \leqq 10^9\right)$ 代表初始序列。
第三行输入一个整数 m(0≦m≦104) 代表操作次数。
此后 m 行,第 i 行输入一条操作,格式为以下两种之一:
∙add a:在序列末尾添加整数 a(−109≦a≦109);
∙mid:输出当前序列的中位数。
输出格式
对于每次 mid 操作,新起一行输出一个整数代表当时序列的中位数。所有答案按操作的先后顺序输出。
测试样例
6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid
5
13
样例 1 解释
初始序列为 {1,2,13,14,15,16}。前两次操作依次添加 5 和 3,序列变为 {1,2,13,14,15,16,5,3},从小到大排列为 {1,2,3,5,13,14,15,16}。此时长度为 8,正中间两个数为 5 和 13,取较小的 5,因此第一次输出 5。
随后添加 20,序列长度为 9,从小到大排列为 {1,2,3,5,13,14,15,16,20},正中间的数为 13,因此第二次输出 13。
5
7 1 4 9 2
5
add 6
mid
add 0
add -3
mid
4
2
样例 2 解释
初始序列为 {7,1,4,9,2}。添加 6 后长度为 6,从小到大排列为 {1,2,4,6,7,9},正中间两个数为 4 和 6,取较小的 4,因此第一次输出 4。
随后依次添加 0 和 −3,长度为 8,从小到大排列为 {−3,0,1,2,4,6,7,9},正中间两个数为 2 和 4,取较小的 2,因此第二次输出 2。
提示
对于 30% 的数据,1≦n≦104,0≦m≦103;对于 100% 的数据,1≦n≦105,0≦m≦104。
序列中的整数绝对值不超过 109,且可能有重复。