[KTST 2025] 뗏목

문제 링크

 

문제 설명

높이 $h$, 너비 $d$의 직사각형을 $(h, d)$이라고 하자. $A$에서 얻은 직사각형 $(h_1, d_1)$과 $B$에서 얻은 직사각형 $(h_2, d_2)$를 조합하면 $\min(h_1, h_2) (d_1+d_2)$의 안정성을 얻는다. $A$ 혹은 $B$에서 원소를 사용하지 않는 경우, 해당 직사각형은 $(\infty , 0)$으로 간주한다.

다음을 만족하는 $(h, l, r)$을 수열 $X$의 maximal rectangle이라고 하자.

 

1. $h = \min(X_l, \cdots, X_r)$

2. $X_{l-1}, X_{r+1} < h$

Maximal rectangle의 높이/너비만 나타내는 경우에는 $(h, d)$로 쓰고, 높이/왼쪽 끝/오른쪽 끝을 나타내는 경우에는 $(h, l, r)$로 나타내자. $A$의 maximal rectangle $(h, d)$의 집합을 rectA, $B$의 maximal rectangle $(h, l, r)$의 집합을 rectB라고 하자.

 

$(h_2, d_2) = (\infty, 0)$인 경우 최대 안정성은 rectA의 $(h, d)$에 대해서 $hd$이다. 이제 $(h_2, d_2) \neq (\infty, 0)$인 경우만 고려하자.

 

B의 maximal rectangle에 따른 케이스 나누기

$B[l \cdots r]$의 maximal rectangle은 $B$의 maximal rectangle $(h', l', r')$과 $[l, r]$의 교집합이다. 3가지로 나눠서 생각하자.

1. $[l, r]$가 $[l', r']$을 포함함
2. $[l', r']$가 $[l, r]$을 포함함
3. $[l, r]$과 $[l', r']$가 겹치지만 포함관계가 아님.

 

1번의 경우,  rectB의 각 $(h', l', r')$에 대해 $(h', r'-l'+1)$으로 만들 수 있는 뗏목의 최대 안정성 구하자. $[l, r]$이 포함하는 $[l', r']$에 대한 최대 뗏목의 안정성은 segment tree sweeping으로 쉽게 구할 수 있다.

2번의 경우, $B[l..r]$의 최소 높이를 $h$라고 하자. $(h, r-l+1)$으로 만들 수 있는 뗏목의 최대 안정성을 구하자.

 

1번과 2번에서 rectB의 $(h, d)$으로 만들 수 있는 뗏목의 최대 안정성을 구해야 한다. rectA의 원소를 $(h', d')$에 대해,

• $h' \ge h$인 경우에는 $h \cdot (\max_{h' \ge h}(d') + d)$가 최대 안정성이고, 이는 $O(\log N)$에 구할 수 있다.
• $h' < h$인 경우에는 $\max_{h' < h}(h'(d'+d))$을 구해야 한다. 이는 $h' < h$인 직선 $y = h'x + h'd'$의 $x=d$일 때 최댓값을 구하는 문제로 변환되며, persistent convex hull을 $O(N \log N)$에 구축해 $O(\log N)$에 구할 수 있다.

$f(h, d) = \max_{h' < h}(h'(d'+d))$으로 정의하자.

 

트리 위에서의 문제로 환원

3번의 경우, 일반성을 잃지 않고 $l < l' \le r < r'$이라고 가정하자.
B의 maximal rectangle로 얻어지는 구간 $(l', r')$은 laminar set family를 이룬다. 쉽게 말해서 포함관계로 트리 구조를 만들 수 있다.
$l < l' \le r < r'$을 만족하는 $(l', r')$은 루트에서 리프로 향하는 경로를 이룬다.
다음 3가지 사실을 통해 우리는 쿼리당 로그제곱에 문제를 풀 수 있다.

1. Heavy Light Decomposition을 통해 트리를 여러 개의 chain으로 쪼갤 수 있다. 이 때 하나의 경로는 $O(\log M)$개의 prefix와 하나의 구간으로 나누어진다.
2. 길이 $t$의 chain에 $q$개의 $(\text{prefix}, r)$ 쿼리가 주어진다고 하자. prefix에 있는 maximal rectangle $(h', l', r')$에 대해 $(h', l', r)$로 만들 수 있는 최대 안정성을 구해야 한다.
   이는 offline query로 $O(q(\log M + \log N) + t \log M \log N)$에 해결할 수 있다.
3. chain에 포함되는 경로 $S$와 $r$이 주어진다. $S$에 포함되는 maximal rectangle $(h', l', r')$에 대해 $[h', l', r]$로 만들 수 있는 최대 안정성을 전처리 $O(M \log M \log N)$, 쿼리 당 $O(\log M \log N)$에 구할 수 있다.

 

첫번째 사실은 Heavy Light Decomposition에 대한 잘 알려진 사실이므로, 설명을 생략한다.

 

chain의 prefix에 대한 sweeping

rectB의 원소 $[h', l', r']$과 rectA의 원소 $(h_a, d_a)$에 대해서, $h' \cdot (\max_{h_a \ge h'} (d_a) + r - l' + 1)$과 $f(h', r - l'+1)$의 최댓값을 구해야 한다.

 

전자는 $r$에 대한 일차식이다. 따라서 평범한 convex hull trick + sweeping으로 $O(t + q \log M)$에 구할 수 있다.

 

$f(h_1, x - l_1)$과 $f(h_2, x - l_2)$의 대소비교는 특정 $x$를 기준으로 나뉜다. 따라서 $f(h, x-l)$에 대한 convex hull을 관리하고, $x=r+1$일 때의 값을 구하면 된다.
$f(h_1, x - l_1)$과 $f(h_2, x - l_2)$의 교점은 이분탐색을 통해 $O(\log M \log N)$에 구할 수 있다. 따라서 convex hull을 유지하는데 $O(t \log M \log N)$의 시간이 든다.
각 쿼리당 convex hull에서 $x$값에 해당하는 $f(h, x - l)$을 찾는데 이분탐색으로 $O(\log M)$, 해당 $h$, $l$에 대해서 $f(h, x - l)$을 구하는데 $O(\log N)$의 시간이 필요하다. 따라서 쿼리당 $O(\log M + \log N)$의 시간복잡도에 해결할 수 있다.

 

segment tree의 구축

앞과 같이 $x$에 대한 일차식과 $f(h, x - l)$를 유지하는 convex hull을 각 세그먼트 트리 노드에 만들자. 길이 $t_1, t_2$의 convex hull을 합치는 것을 $O((t_1 + t_2) \log N)$ 시간에 해결하면 된다.

 

직선을 유지하는 convex hull을 합치는 것은 쉽다. 첫 번째 convex hull에 두 번째 convex hull에 있는 직선들을 순차적으로 추가하면 된다. $O(t_1 + t_2)$에 할 수 있다.

 

$f(h, x - l)$을 유지하는 convex hull을 합치는 것은 조금 어렵다. 각 $f(h, x-l)$의 교차점들의 집합을 $pos = (x_1, x_2, \dots, x_k)$라고 하자. $pos$에 있는 위치에 대한 convex hull의 값을 구하는 것은 $O((t_1 + t_2) \log N)$에 할 수 있다. 이를 통해 2개의 convex hull이 $x_i$와 $x_{i+1}$ 사이에서 교차함을 알 수 있다. 2개의 $f(h, x - l)$의 교차점을 구하면 되고, 이는 $O(\log M \log N)$에 할 수 있다. segment tree 노드를 합치는 횟수는 $M$번이니, 전체적으로 $O(M \log M \log N)$시간복잡도 내에 segment tree를 구축할 수 있다.

 

하나의 구간 쿼리는 $O(\log M)$개의 노드에 대한 쿼리로 환원된다. 각 convex hull에 대해서 $x$값에 대응하는 최댓값을 구하는데 $O(\log M + \log N)$의 시간이 필요함은 앞에서 보였다.

 

전체 시간복잡도

$O(N \log N + Q \log M (\log M + \log N) + M \log M \log N)$에 문제를 해결할 수 있다.