IOI18 meetings

https://oj.uz/problem/view/IOI18_meetings

길이 $N$의 수열 $H_i$가 있을 때, $L_i$~$R_i$에서의 ‘모임 비용’의 최솟값을 구해야 한다.

이때 모임 비용 $C(L, R, x)$는 다음과 같이 정의된다.

$C(L, R, x) = \sum_{i=L}^{x}max_{i\leq j\leq x}(H_j) + \sum_{i=x+1}^{R}max_{x\leq j\leq E}(H_j)$ $(L\leq x\leq R)$

여기에서 $x$를 모임 장소라고 한다.

수열의 길이 $N$과 쿼리의 개수 $Q$는 $750,000$ 이하, 시간 제한은 4.5s이다.풀이

일단 모든 수들에 서로 다른 작은 수를 더하면 되므로 모든 수들이 다르다고 가정해도 된다.

쿼리 $(L, R)$에 대해서 $m=maxidx_{L\leq i\leq R}(H_i)$로 정의하면, 답은 $min(min(C(L, m - 1, x) + (R - m + 1)A_m), min((m - L + 1)A_m + C(m + 1, R, x)))$이 된다.

$x$가 $m$보다 작을 때와 클 때를 나눈 것이다.

이 사실을 통해 쿼리 $(L, R)$을 쿼리 $(L, m - 1)$과 $(m + 1, R)$으로 나눌 수 있다.

이 쿼리 중 $(m + 1, R)$들을 모두 구할 수 있다면 $(L, m - 1)$은 수열을 뒤집어서 똑같이 구할 수 있다.

이제 쿼리 $(m + 1, R)$만 모아서 다시 $(L, R)$으로 쓰자.

이 $(L, R)$들이 가지는 중요한 특징은 모든 $L\leq i\leq R$에 대해서 $H_i<H_{L-1}$을 만족한다는 것이다.

다음과 같은 함수를 정의하자.

$process(S, E)$ = $S\leq L\leq E$인 모든 쿼리를 처리하고, $f(i)=min_{S\leq x\leq i}(C(S, i, x))$를 반환하는 함수 (다만, 모든 $S\leq i\leq E$에 대해 $H_i\leq H_{S - 1}, H_{E + 1}$을 만족해야 한다.)

$M=maxidx_{S\leq i\leq E}(H_i)$라고 했을 때, process(M + 1, E)의 반환값 $f$를 안다면, $m=M$인 쿼리들의 값을 모두 알 수 있다. 따라서 $process(S, E)$에서 $process(S, M - 1)$과 $process(M + 1, E)$를 호출하면 $S\leq m\leq E$인 모든 쿼리를 처리하는 것이 가능하다.

문제는 $f(i)$를 구해야 한다는 것이다. segment tree의 각 노드에 CHT를 사용하여 $O(N \log N+Q \log^2 N)$에 처리하거나, Li Chao Segment Tree를 사용하여 $O(N \log^2N+Q \log N)$에 처리할 수 있지만, 100점을 받기는 쉽지 않다. (Li-Chao tree를 사용한 방법이 oj.uz에서 4.7s가 나온다) $f(i)$를 $O(N \log N)$에 처리하기 위해 증명할 다음과 같은 중요한 성질이 있다.

$g(x)$를 쿼리 $(L, x)$에서의 최적 모임 장소들 중 가장 왼쪽에 있는 모임 장소라고 할 때, $g(x)$는 단조 증가한다.

쿼리 $(L, x + 1)$의 모임 비용은 쿼리 $(L, x)$에서의 비용과 $x + 1$번 사람이 모임 장소까지 가는 비용의 합이 된다.

쿼리 $(L, x)$에서의 비용은 모임 장소가 최적해에서 왼쪽으로 가면 증가한다. 또한 $x + 1$번 사람이 모임 장소까지 가는 비용도 왼쪽으로 갈수록 단조 증가한다. 따라서 그 합도 왼쪽으로 가면 증가할 것이고, $g(x)$는 감소할 수 없다.

$process(L, M - 1)$에서의 $f(x)$를 $f_L(x)$, $process(M + 1, E)$에서의 $f(x)$를 $f_R(x)$라고 하자.

$f(x)$의 값은 $L\leq x\leq M - 1$일 때는 $f_L(x)$의 값과 같으므로 따로 구해줄 필요가 없다. $f(M)$은 $f_L(M - 1) + H_M$이다. 문제는 $M + 1\leq x\leq E$일 때이다.

위에서 증명한 성질에 의해, 어떤 $y$가 존재하여 $M + 1\leq x\leq y$인 $f(x)$에서는 모임 장소가 $[S, M]$에 있고, $y < x\leq E$인 $f(x)$에서는 모임 장소가 $[M + 1, E]$에 있을 것이다. 모임 장소가 $[S, M]$에 있다면 최소 비용은 $f(M) + (x - M)H_M$으로 계산된다. 이것은 하나의 직선으로 표현될 수 있다. 모임 장소가 $[M + 1, E]$에 있다면 최소 비용은 $(M - S + 1)H_M + f_R(x)$로 계산된다. 이것은 $f_R(x)$에 상수를 더한 값이다.

$f(x)$를 직선의 deque과 더해진 상수 $A$로 관리하면 모든 연산을 총 $O((N + Q) \log N)$에 할 수 있다.

해야 하는 연산은 다음과 같다.

1. $f(x)$의 front에 직선을 추가 : front의 직선부터 보면서 추가된 직선과 비교한다. 추가된 직선이 더 비용이 낮다면 원래 직선을 빼고 반복하며, 원래 있던 직선의 비용이 낮다면 그 앞에 추가된 직선을 넣어줄 수 있다. 위의 증명에 의해 deque의 앞에 있는 직선들만 봐도 충분하다. 한 번의 연산에 최소 한 개의 직선이 없어지므로 amortized $O(N)$이 된다.

2. $f(x)$에 상수를 더함 : $A$에 더해주면 된다. 내부의 값이 필요할 때 직선에 $A$를 더해서 사용하고, 내부에 직선을 넣을 때는 $A$를 뺀 후 넣어주면 된다. $O(1)$에 처리할 수 있다.

3. 두 개의 $f(x)$를 합침 : 작은 deque에서 하나씩 빼서 큰 deque에 넣어주는 방식으로 합칠 수 있다. 잘 알려진 방법으로 시간복잡도는 amortized $O(N \log N)$이 된다.

4. $f(x)$의 값을 구함 : 이분 탐색을 통해 $f(x)$에서 $x$ 값을 담당하는 직선을 $O(\log N)$에 찾을 수 있다. 쿼리마다 한 번 구하므로 $O(Q \log N)$이다.

따라서 시간복잡도 $O((N + Q) \log N)$, 공간복잡도 $O(N + Q)$에 문제를 해결할 수 있다.