Absolute Minima

题目描述

有一个函数 $f(x)$，最初是常数函数 $f(x) = 0$。 我们将按顺序处理 $Q$ 个查询。查询有两种类型：更新查询和求值查询，定义如下：

更新查询 $1 a b$：给定两个整数 $a$ 和 $b$，令 $g(x) = f(x) + |x - a| + b$，并用 $g(x)$ 替换 $f(x)$。 求值查询 $2$：输出使 $f(x)$ 最小化的 $x$，以及 $f(x)$ 的最小值。如果存在多个这样的 $x$，请选择最小的那个。

我们可以证明在求值查询中要输出的值总是整数，因此请以整数形式（不带小数点）输出这些值。

输入格式

输入通过标准输入按以下格式给出： $Q$ $Query_1$ : $Query_Q$

参见样例输入 1 以了解示例。

输出格式

对于每个求值查询，按查询给出的顺序输出一行响应。 每个求值查询的响应应为使 $f(x)$ 最小的最小的 $x$ 值，以及 $f(x)$ 的最小值，按此顺序输出，两者之间用空格分隔。

4
1 4 2
2
1 1 -8
2

4 2
1 -3

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

-1000000000 3000000000

提示

输入中的所有值都是整数。 $1 \leq Q \leq 2 \times 10^5$ $-10^9 \leq a, b \leq 10^9$ 第一个查询为更新查询。在第一个求值查询中，$f(x) = |x - 4| + 2$，它在 $x = 4$ 处取得最小值 $2$。 在第二个求值查询中，$f(x) = |x - 1| + |x - 4| - 6$，当 $1 \leq x \leq 4$ 时取得最小值 $-3$。在多个最小化 $f(x)$ 的 $x$ 中，我们要求你输出最小的那个，即 $1$。

标签: AtCoder|abc127F

来源

AtCoder|abc127F