← 返回题目列表

AtCoder · abc127_f

F. 绝对最小值

中文机器翻译题面 查看原题

分数: 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