수중 정원 — NYPC 2021

다오는 게임의 대규모 패치를 준비하고 있다. 대규모 패치의 내용은 수중 정원의 오픈으로, 수중 정원은 아름다운 해저의 모습을 볼 수 있는 여러 맵으로 이루어질 예정이다.

이미 수중 정원 전체의 디자인은 모두 완성되었다. 일직선 형태로 쭉 이어진 형태의 수중 정원은 수심이 계속 변화하는 형태로 다양한 바다 풍경을 유저에게 제공한다. 이에 따라, 수중 정원에서 각 맵의 매력도는 그 맵에서 가장 깊은 수심과 가장 얕은 수심의 차이로 정의된다. 이 값이 클수록 더 다양한 풍경을 볼 수 있기 때문이다. 다오는 수심에 대한 정보가 $N$ 개 있는 수중 정원을 $K$ 개의 맵으로 분할하여 모든 맵의 매력도의 합을 최대화하고자 한다.

다오는 다음과 같이 문제를 추상화하였다. 수중 정원 전체를 맨 왼쪽에서부터 쭉 보았을 때 각 지역의 수심을 나열하여 크기 $N$ 인 정수 수열로 볼 수 있을 것이다. 이 수열을 $H = H_1, H_2, .., H_N$ 이라고 하자. 이때, 이 수열을 연속한 구간 $K$ 개로 나누어 각 구간 내에서 최댓값과 최솟값의 차이들의 합을 최대화하는 것이 다오의 목적이다.

예를 들어, $N = 5$ , $K = 2$ , $H = [2, 4, 1, 4, 3]$ 인 경우를 생각해보자. 맵을 $[2, 4, 1], [4, 3]$ 의 둘로 나누었다면 두 맵의 매력도는 각각 $3, 1$ 이 되어 그 합이 $4$ 가 된다. 한편, 맵을 $[2, 4], [1, 4, 3]$ 의 둘로 나눈 경우 두 맵의 매력도는 $2, 3$ 이 되어 그 합이 $5$ 이다. 매력도의 합이 $5$ 보다 커지도록 두 맵으로 나누는 것은 불가능하므로 $5$ 가 매력도의 합의 최댓값이다.

맵의 개수는 다오가 혼자서 정할 수 없기 때문에, 다오는 가능한 모든 $K$ 에 대해서 수중 정원을 $K$ 개의 맵으로 나눌 때 매력도 합의 최댓값을 구해놓고자 한다. 다오를 도와 $K = 1, 2, .., N$ 인 $N$ 가지 경우에 대해 매력도 합의 최댓값을 구하여라.

입력 형식

첫 줄에 수중 정원의 크기 $N$ 이 주어진다. $(1 \le N \le 200\,000)$

둘째 줄에 수중 정원에 대한 정보를 나타내는 $N$ 개의 정수 $H_1, H_2, .., H_N$ 가 공백으로 구분되어 주어진다. $(1 \le H_i \le 10^9)$

출력 형식

$N$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에 수중 정원을 $i$ 개의 맵으로 나누는 경우 매력도 총합의 최댓값을 출력한다.

예제

입력

5 2 4 1 4 3

출력

3 5 5 3 0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 18점

$1 \le N \le 300$

종류 2: 23점

$1 \le N \le 5\,000$

종류 3: 59점

추가적인 제한 조건이 없음.

해설

문제를 추상화시키면 아래와 같이 표현할 수 있다:

길이 $N$ 인 수열 $A_1$ , $A_2$ , ..., $A_N$ 이 있을 때 이 수열을 $K$ 개의 부분으로 나누어 각 부분의 (최댓값 - 최솟값)의 합을 최대화시킬 때 $K = 1$ , $2$ , $3$ , ..., $N$ 인 경우에 대해 각각 그 값을 구하여라.

수열을 $K$ 개의 부분으로 나눈 상태를 생각해보자. 각 부분에서 최댓값에 +, 최솟값에 - 마크를 붙인다면, + 를 붙인 수를 모두 더하고 -를 붙인 수는 모두 뺐을때 그 값은 (최댓값 - 최솟값)의 합과 같다. 조금 더 생각해보면, 각 부분에 + 마크와 - 마크를 하나씩 붙이는 경우 중 최댓값에 +, 최솟값에 -를 붙일 때가 최종 계산한 값이 가장 최대가 됨을 알 수 있다.

이제 반대로 + 마크와 - 마크를 먼저 부여했을 때 수열을 $K$ 개로 나누어 각 수열이 + 마크와 - 마크를 정확히 하나 갖도록 나눌 수 있는 필요충분조건을 생각해보면, + 마크와 - 마크가 총 $K$ 개이고 또한 앞에서부터 몇 개의 수를 보았을 때 + 개수와 - 개수의 차이가 $1$ 을 초과하지 않는다면 가능함을 알 수 있다.

따라서, 본 문제는 수열의 각 원소에 +, -, 또는 +와 - 모두를 부여할 수 있고 +와 -를 각각 정확히 $K$ 개 부여하면서, 모든 $1$ 이상 $N$ 이하의 $i$ 에 대해 첫 $i$ 개 원소에 붙은 + 마크와 - 마크 개수의 차가 $1$ 이하가 될 때 계산 결과를 최대화하는 문제와 같다. 그러면 아래와 같은 간단한 풀이를 얻을 수 있다:

$D[i][j][k]$ : $i$ 번째 수까지 (+ 개수)가 $j$ 개, (- 개수) $-$ (+ 개수)가 $k$ 일 때의 최댓값

으로 놓으면 $k$ 는 $-1$ , $0$ , $1$ 중 하나인 경우만 확인하면 되기 때문에 $\mathcal{O}(N^2)$ 시간에 문제를 해결할 수 있다.

속도를 개선하는 방법은 수열 $A_l$ , …, $A_r$ 에 대한 답을 $A_l$ , …, $A_{mid}$ 에 대한 답과 $A_{mid+1}$ , …, $A_r$ 에 대한 답으로부터 구하는 것이다. 즉 분할 정복을 사용하는 것이다.

수열을 $K$ 개의 블록으로 나누어 각 블록에 + 마크와 - 마크를 한개씩 붙였다고 가정하고, $A_l$ , ..., $A_r$ 를 따로 떼서 보면, $A_l$ , .., $A_r$ 이 완전히 포함하는 블록들의 경우에는 그 블록의 + 와 - 가 모두 $A_l$ , ..., $A_r$ 의 원소 중 하나에 붙어있을 것이고, 그렇지 않은 블록은 최대 2개 (맨 왼쪽 부분이 포함된 블록, 맨 오른쪽 부분이 포함된 블록)가 있을 수 있다.

따라서, $A_l$ , .., $A_r$ 에서 서로 같은 블록의 + 마크와 - 마크 짝을 제외하고 본다면,

맨 왼쪽에 추가적인 +가 있는 경우 / -가 있는 경우 / 없는 경우
맨 오른쪽에 +가 있는 경우 / -가 있는경우 / 없는 경우

의 $3$ 가지 $\times$ $3$ 가지, 즉 $9$ 가지 경우가 나온다. 각 경우를 (+, -), (+, .), (+, -), (., +), (., .), (., -), (-, +), (-, .), (-, -)와 같이 표현하자.

이 $9$ 가지 케이스에 대해 각각 +, - 개수 짝이 $0$ , $1$ , .., $r-l+1$ 개인 경우에 대한 답을 저장해놓으면 $A_l$ , ..., $A_{mid}$ 와 $A_{mid+1}$ , ..., $A_r$ 에 대한 답들로부터 $A_l$ , ..., $A_r$ 에 대한 답을 구할 수 있다.

예를 들어, $A_l$ , ..., $A_r$ 에서 (-, +) 케이스는

$A_l$ , ..., $A_{mid}$ 의 (-, .) 케이스와 $A_{mid+1}$ , ..., $A_r$ 의 (., +) 케이스
$A_l$ , ..., $A_{mid}$ 의 (-, -) 케이스와 $A_{mid+1}$ , ..., $A_r$ 의 (+, +) 케이스
$A_l$ , ..., $A_{mid}$ 의 (-, +) 케이스와 $A_{mid+1}$ , ..., $A_r$ 의 (-, +) 케이스

의 $3$ 가지 중 하나에 해당된다. 즉 이 $3$ 가지 방법으로 계산된 값의 최댓값을 구하면 $A_l$ , ..., $A_r$ 의 (-, +) 케이스의 답을 구할 수 있다.

합쳐서 답을 구하는 작업을 그냥 하면 $\mathcal{O}(N^2)$ 시간이 걸리는데, 각 케이스에서 +, - 개수 짝에 대한 답을 나열하면 이 답은 convex하다는 성질을 띈다. 이는 위 과정처럼 두 convex function $f$ 와 $g$ 에 대해 $h(i) = \max(f(x) + g(i-x))$ 가 되도록 합치면 $h$ 가 convex function이 되고, 여러 convex function의 최댓값을 구해도 convex function이 되기 때문이다. 크기가 $N$ 과 $M$ 인 convex function을 합치는 것은 $\mathcal{O}(N+M)$ 시간에 가능하기 때문에, 총 문제를 $\mathcal{O}(N \log N)$ 시간에 해결할 수 있다.

한편, 함수값이 convex함은 이 문제를 최소 비용 최대 유량 문제로 모델링 가능하기 때문에 이를 통해서 추측이 가능하고 이를 통해 접근할 수 있다.