Processing math: 6%
본문 바로가기

ps (문제)

[KTST 2025] 뗏목

문제 링크

 

문제 설명

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

maximal rectangle이란?

다음을 만족하는 (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에 포함되는 경로 Sr이 주어진다. 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_ix_{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)에 문제를 해결할 수 있다.

 

'ps (문제)' 카테고리의 다른 글