문제 설명
높이 h, 너비 d의 직사각형을 (h,d)이라고 하자. A에서 얻은 직사각형 (h1,d1)과 B에서 얻은 직사각형 (h2,d2)를 조합하면 min의 안정성을 얻는다. 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가지로 나눠서 생각하자.
- [l, r]가 [l', r']을 포함함
- [l', r']가 [l, r]을 포함함
- [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가지 사실을 통해 우리는 쿼리당 로그제곱에 문제를 풀 수 있다.
- Heavy Light Decomposition을 통해 트리를 여러 개의 chain으로 쪼갤 수 있다. 이 때 하나의 경로는 O(\log M)개의 prefix와 하나의 구간으로 나누어진다.
- 길이 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)에 해결할 수 있다. - 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)에 문제를 해결할 수 있다.
'ps (문제)' 카테고리의 다른 글
색종이 붙이기 (0) | 2024.10.18 |
---|---|
[IOI 2024] Hieroglyphs (0) | 2024.09.23 |
아인타, 빈타, 그리고 씬타 (0) | 2024.09.20 |
USACO 2024 January Contest (Gold Division) (0) | 2024.05.28 |
RUN 2024 Spring Contest 풀이(내가 출제한 문제들) (0) | 2024.05.08 |