分数: 600 点
问题陈述
有一个功能 f(x),最初是一个常数函数 f(x) = 0.
我们将要求您处理 Q 按顺序查询。查询有两种,更新查询和评估查询,如下:
- 更新查询
1 a b:给定两个整数 a 和 b,让 g(x) = f(x) + |x - a| + b 并替换 f(x) 与 g(x). - 评估查询
2:打印 x 最小化 f(x),以及最小值 f(x)。如果有多个这样的值 x,选择该值的最小值。
我们可以证明,评估查询中要输出的值始终是整数,因此我们要求您将这些值打印为不带小数点的整数。
约束
- 输入中的所有值都是整数。
- 1 \leq Q \leq 2 \times 10^5
- -10^9 \leq a, b \leq 10^9
- 第一个查询是更新查询。
输入
输入由标准输入按以下格式给出:
Q Query_1 : Query_Q
有关示例,请参阅示例输入 1。
输出
对于每个评估查询,按照给出查询的顺序打印包含响应的行。
每个评估查询的响应应该是以下最小值 x 最小化 f(x),以及最小值 f(x),按此顺序,中间有空格。
示例输入 1
4 1 4 2 2 1 1 -8 2
示例输出 1
4 2 1 -3
在第一个评估查询中, f(x) = |x - 4| + 2,达到最小值 2 at x = 4.
在第二个评估查询中, f(x) = |x - 1| + |x - 4| - 6,达到最小值 -3 当 1 \leq x \leq 4。在多个值中 x 最小化 f(x),我们要求您打印最小值,即 1.
示例输入 2
4 1 -1000000000 1000000000 1 -1000000000 1000000000 1 -1000000000 1000000000 2
示例输出 2
-1000000000 3000000000