8841: [yosupo] Data Structure - Line Add Get Min
[Creator : ]
Description
There are $N$ straight lines $y = a_i x + b_i$. Process $Q$ queries.
- 0 $a$ $b$: Add a straight line $y = ax + b$.
- 1 $p$: Find the minimal $y$ at $x = p$.
- 0 $a$ $b$: Add a straight line $y = ax + b$.
- 1 $p$: Find the minimal $y$ at $x = p$.
Input
$N$ $Q$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{N-1}$ $b_{N-1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{N-1}$ $b_{N-1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
Constraints
$1 \leq N, Q \leq 200000$
- $|a_i|, |p| \leq 10^{9}$
- $|b_i| \leq 10^{18}$
- $|a_i|, |p| \leq 10^{9}$
- $|b_i| \leq 10^{18}$
Sample 1 Input
2 8
-1 -1
0 1
1 -1
1 -2
1 0
1 2
0 0 -10
1 -2
1 0
1 2
Sample 1 Output
0
1
-1
-3
-10
-10
-10