문제 73
직선의 최솟값
빈 직선 집합 $S$가 있다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
1 a b: 직선 $y=ax+b$를 $S$에 추가한다.2 x: $S$에 있는 직선 중 $x$에서의 $y$값의 최솟값을 출력한다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
각 쿼리는 1 a b 또는 2 x 형식으로 주어지며, 각 값은 공백으로 구분되어 주어진다. 1 a b에서는 $(-10^9 \le a, b \le 10^9)$, 2 x에서는 $(-10^9 \le x \le 10^9)$이다.
1 a b 쿼리에서 추가되는 직선의 기울기 $a$는 입력 순서대로 엄격하게 감소한다.
2 x 쿼리는 직선이 하나 이상 추가된 뒤에만 주어진다.
출력
2 x 쿼리마다 최솟값을 한 줄에 하나씩 출력한다.
예제 입력 1
9 1 5 0 1 3 6 2 0 2 2 1 1 1 2 2 2 10 1 -1 30 2 10
예제 출력 1
0 10 3 11 11
공식 해설
최솟값이 될 수 없는 직선 제거하기
직선의 기울기가 감소하는 순서로 추가된다. 기울기가 큰 직선은 왼쪽에서, 작은 직선은 오른쪽에서 유리하므로 최솟값을 만드는 직선들을 순서대로 저장하는 Convex Hull Trick을 사용할 수 있다.
세 직선의 기울기가 $a_1>a_2>a_3$일 때, 첫째와 둘째의 교점이 둘째와 셋째의 교점보다 오른쪽에 있거나 같으면 둘째 직선이 혼자 최솟값이 되는 구간은 없다. 교점의 분모가 양수이므로 이 조건은
\[
(b_2-b_1)(a_2-a_3)\ge(b_3-b_2)(a_1-a_2)
\]
로 비교할 수 있다.
새 직선을 넣을 때 마지막 두 직선과 이 조건을 검사하고, 가운데 직선이 불필요하면 제거한다. 이를 반복한 뒤 새 직선을 넣으면 남은 직선들의 인접 교점이 증가한다. 교점 자체를 근삿값으로 구하지 않고 위의 정수 곱을 정확히 비교하면 반올림으로 순서가 바뀌는 문제를 피할 수 있다.
임의의 위치에서 이분 탐색하기
질의 $x$는 증가하는 순서가 아니므로 포인터를 한 방향으로만 옮겨서는 안 된다. 남은 직선들의 값을 비교하여 최솟값의 위치를 이분 탐색한다.
인접 교점들이 증가하므로 고정한 $x$에서 직선 값들은 최솟값까지 감소하다가 증가한다. 중간 직선의 값이 다음 직선의 값 이상이면 오른쪽으로, 아니라면 왼쪽으로 탐색 범위를 줄인다. 마지막 직선의 $ax+b$를 출력한다.
각 직선은 한 번 추가되고 최대 한 번 제거되며, 질의는 로그 시간이다. 전체 시간복잡도는 $O(Q\log(Q+1))$, 공간복잡도는 $O(Q)$이다. 직선 값 $ax+b$와 교점 비교의 중간 곱은 모두 정수로 정확히 계산해야 한다.
구현 · 언어별 풀이
C++ 구현
직선의 기울기와 절편은 long long으로 저장하고 후보들은 vector에 유지한다. 교점 비교의 차끼리의 곱은 최대 $4\cdot10^{18}$로 long long에 들어가며, 곱하기 전부터 이 자료형으로 계산한다. 질의에서는 이웃한 두 직선의 $ax+b$를 비교해 이분 탐색한다.
C 구현
직선의 $a$, $b$와 $ax+b$는 long long으로 계산한다. 입력 범위에서 차끼리의 곱도 최대 $4 \cdot 10^{18}$이므로 long long에 들어가지만 곱하기 전에 승격해야 한다. 교점 나눗셈 대신 교차곱으로 뒤 직선의 불필요 여부를 검사하고 질의는 이분 탐색한다.
Python 구현
직선을 $(a,b)$의 튜플로 저장하고 교차곱은 int로 계산한다. 교점 float를 저장하지 않는다. 질의 $x$는 단조가 아니므로 앞 원소를 계속 pop하는 방식 대신 인접 직선의 $ax+b$를 비교하여 이분 탐색한다.
Java 구현
$a$, $b$와 $ax+b$는 long으로 둔다. 차의 절댓값은 $2 \cdot 10^{9}$ 이하라 교차곱은 $4 \cdot 10^{18}$ 이하이다. 곱하기 전부터 long으로 계산하고, 질의 위치는 이분 탐색한다.
Rust 구현
$a$, $b$와 함수값은 i64로 저장한다. 입력 범위상 교차곱도 i64에 들어가며 실수 교점을 만들지 않는다. 질의 $x$의 순서는 보장되지 않으므로 hull을 지우지 않고 이분 탐색한다.
JavaScript 구현
기울기·절편·질의 좌표는 토큰에서 BigInt로 읽는다. 값 $ax+b$도 안전 정수 범위를 넘을 수 있고, 불필요한 직선을 제거하는 교차 곱은 더 커진다. 교점 좌표를 부동소수로 나누어 저장하지 않는다.
기울기가 엄격히 감소하므로 직선을 배열 뒤에 추가하고, 공통 풀이의 교차 곱 조건에 따라 불필요한 가운데 직선을 pop()한다.
질의의 $x$는 증가한다는 보장이 없다. 이동 포인터 대신 인접 두 직선의 값으로 이분 탐색한다. f(mid, x) <= f(mid + 1, x)이면 오른쪽 경계를 mid로 옮기고, 아니면 왼쪽을 mid + 1로 옮긴다. 배열 인덱스만 Number로 두며, 결과는 문자열로 출력한다.