[ABC127F] Absolute Minima
题意翻译
### 题目描述
有一个函数 $f(x)$ ,初始时 $f(x)=0$
接下来你会对这个函数进行 $Q$ 次以下操作:
- $\texttt{1 a b}$,将 $f(x)$ 替换为 $g(x)=f(x)+|x-a|+b$
- $\texttt{2}$,询问最小的整数 $x$ ,使得 $f(x)$ 取到最小值,以及 $f(x)$ 的最小值
### 输入格式
第一行一个整数 $Q$
接下来 $Q$ 行,每行一个或三个整数,表示一次操作。
### 输出格式
对于每一次询问,输出一行两个整数,分别表示最小的整数 $x$ ,使得 $f(x)$ 取到最小值,和 $f(x)$ 的最小值
### 数据范围与提示
$1 \le Q \le 200000,-10^9 \le a,b \le 10^9$ ,保证第一次操作一定是修改操作
题目描述
[problemUrl]: https://atcoder.jp/contests/abc127/tasks/abc127_f
関数 $ f(x) $ があります。 はじめ、これは定数関数 $ f(x)\ =\ 0 $ です。
$ Q $ 個のクエリが与えられるので、順番に処理してください。クエリは $ 2 $ 種類あり、入力形式とクエリの内容は以下の通りです。
- 更新クエリ `1 a b`: 2整数 $ a $, $ b $ が与えられるので、$ g(x)\ =\ f(x)\ +\ |x\ -\ a|\ +\ b $ として $ f(x) $ を $ g(x) $ で置き換える。
- 求値クエリ `2`: $ f(x) $ の最小値を与える $ x $、および $ f(x) $ の最小値を出力する。ただし、そのような $ x $ が複数存在する場合には最小の $ x $ を答える。
この時、求値クエリにおいて出力すべき値は常に整数となることが示せます。 したがって、出力する際は小数点を用いず、整数で出力してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ Q $ $ Query_1 $ $ : $ $ Query_Q $
実例は入出力例 1 を参照せよ。
输出格式
求値クエリに対する応答を、クエリが与えられた順にそれぞれ 1 行で出力せよ。
各求値クエリに対する応答では、$ f(x) $ の最小値を与える最小の $ x $、および $ f(x) $ の最小値を空白スペース区切りで出力すること。
输入输出样例
输入样例 #1
4
1 4 2
2
1 1 -8
2
输出样例 #1
4 2
1 -3
输入样例 #2
4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2
输出样例 #2
-1000000000 3000000000
说明
### 制約
- 入力は全て整数
- $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $
- $ -10^9\ \leq\ a,\ b\ \leq\ 10^9 $
- $ 1 $ 番目のクエリは更新クエリである
### Sample Explanation 1
$ 1 $ つ目の求値クエリにおいて、$ f(x)\ =\ |x\ -\ 4|\ +\ 2 $ となっています。 したがって $ x\ =\ 4 $ において最小値 $ 2 $ を取ります。 $ 2 $ つ目の求値クエリでは、$ f(x)\ =\ |x\ -\ 1|\ +\ |x\ -\ 4|\ -\ 6 $ となっており、$ x $ が $ 1\ \leq\ x\ \leq\ 4 $ を満たすならば最小値 $ -3 $ を与えます。この時、最小値を与える $ x $ が複数存在していますが、その中で最小の値である $ 1 $ を出力してください。