A7680. Chalkboard Median
编程题
入门
知识点
题目描述
黑板上写有一个整数 $X$。
你需要依次处理 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）如下：
> 给定两个整数 $A_i$ 和 $B_i$，将这两个新整数写在黑板上。
>
> 然后，输出此时黑板上所写的 $2i+1$ 个整数的中位数。
你需要依次处理 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）如下：
> 给定两个整数 $A_i$ 和 $B_i$，将这两个新整数写在黑板上。
>
> 然后，输出此时黑板上所写的 $2i+1$ 个整数的中位数。
输入格式
输入从标准输入中按以下格式给出：
> $X$
> $Q$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_Q$ $B_Q$
> $X$
> $Q$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_Q$ $B_Q$
输出格式
输出 $Q$ 行。
第 $i$ 行应包含第 $i$ 个查询的答案。
第 $i$ 行应包含第 $i$ 个查询的答案。
输入输出样例
输入 #1
5 3 2 3 1 2 8 9
输出 #1
3 2 3
输入 #2
1 4 2 3 4 5 6 7 8 9
输出 #2
2 3 4 5
输入 #3
278117031 7 167642909 517897721 148434323 567739597 319926999 481642530 659199879 252516557 49913403 798318034 89701408 892537201 199166668 742285869
输出 #3
278117031 278117031 319926999 319926999 319926999 319926999 319926999
说明/提示
**样例 1 解释：**
在第一次查询中，黑板上写的整数变为 $5, 2, 3$，它们的中位数为 $3$。
在第二次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2$，它们的中位数为 $2$。
在第三次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2, 8, 9$，它们的中位数为 $3$。
### 限制条件
* $1 \le X \le 10^9$
* $1 \le Q \le 2 \times 10^5$
* $1 \le A_i, B_i \le 10^9$
* 所有输入值均为整数。
在第一次查询中，黑板上写的整数变为 $5, 2, 3$，它们的中位数为 $3$。
在第二次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2$，它们的中位数为 $2$。
在第三次查询中，黑板上写的整数变为 $5, 2, 3, 1, 2, 8, 9$，它们的中位数为 $3$。
### 限制条件
* $1 \le X \le 10^9$
* $1 \le Q \le 2 \times 10^5$
* $1 \le A_i, B_i \le 10^9$
* 所有输入值均为整数。