링크

Rooted Tree에서는 노드의 번호를 다시 매겨서 모든 노드에 대해 노드의 자손을 하나의 구간으로 나타낼 수 있습니다. 이는 노드의 번호를 DFS 방문 순서로 나타내는 것으로 가능합니다. 이제 BIT를 이용한 구간 갱신을 통해 특정 사람의 월급을 바로 계산할 수 있습니다.

링크

한 부분만 볼 때, 양쪽의 높이가 $h_{1}, h_{2} (h_{1} < h_{2})$이라고 하고 입력으로 주어진 물의 높이가 $h$라면 물의 넓이는 다음의 세 가지 경우가 있을 수 있습니다.

$$ \begin{cases} 0 & \text{if }h \leq h_{1} \\ \dfrac{(h-h_{1})^{2}}{2(h_{2}-h_{1})} & \text{if }h_{1} \lt h \lt h_{2} \\ h-\dfrac{h_{1}+h_{2}}{2} & \text{if }h_{2} \leq h \end{cases} $$

이제 식을 풀어서 $ h^2, h, $ 상수항에 대해 계수의 합을 BIT로 유지해주면 됩니다.

링크

2번 자동차부터 지연이 발생합니다. $j$번 자동차를 만들 때 생기는 지연을 $ \alpha_{j} $라고 하면 사원 $i$에 대해 $ \alpha_{j} $가 만족해야 하는 조건은

$$ S_{i} = \sum_{k=1}^{i} {T_{k}} $$ 라고 하면

$$ S_{i} F_{j-1} \leq \alpha_{j}+ S_{i-1}F_{j} $$ 을 만족해야 하므로 ($j-1$번 자동차를 만드는 시점을 0초라고 할 떄 $i$번 사원이 $j-1$번 자동차의 부품을 끝내는 시점이 좌변, $i-1$번 사원이 $j$번 자동차의 부품을 끝내고 넘어오는 시간이 우변)

$$ \alpha_{j} = \max_{i=1}^{N} {\left( S_{i} F_{j-1}-S_{i-1}F_{j} \right) } $$ 을 만족해야 합니다. (모든 사원이 만족하도록)

$$ C(i,j) = S_{i} F_{j-1}-S_{i-1}F_{j} $$ 라고 하고, $ i_{1} < i_{2} $인 $ i_{1} , i_{2} $에 대해 $ C(i_{1},j) \leq C(i_{2},j) $을 만족할 조건을 구해봅니다 $$ \begin{align} & C(i_{1},j) \leq C(i_{2},j) \\ \Leftrightarrow & \; S_{i_{1}} F_{j-1}-S_{i_{1}-1}F_{j} \leq S_{i_{2}} F_{j-1}-S_{i_{2}-1}F_{j} \\ \Leftrightarrow & \; \left(S_{i_{2}-1}-S_{i_{1}-1}\right)F_{j} \leq \left(S_{i_{2}}-S_{i_{1}}\right) F_{j-1} \\ \Leftrightarrow & \; \frac{S_{i_{2}-1}-S_{i_{1}-1}}{S_{i_{2}}-S_{i_{1}}} \leq \frac{F_{j-1}}{F_{j}} \\ \Leftrightarrow & f(i_{1},i_{2}) \leq g(j) \end{align} $$

꼴로 $i_{1},i_{2}$의 항과 $j$의 항으로 따로 떼어놓을 수 있습니다. 이제 $i$를 $1$부터 $N$까지 순서대로 다음을 만족하도록 유지하여 $i_{1}, \ldots ,i_{K}$를 만듭니다.

$$ f(i_{1},i_{2}) < f(i_{2},i_{3}) < \ldots < f(i_{K-1},i_{K}) $$

이제 이분검색으로 $ f(i_{l-1},i_{l}) \leq g(j) \leq f(i_{l},i_{l+1}) $인 $l$을 찾으면 $ \alpha_{j} = C(i_{l},j) $가 됩니다. 답은

$$ \sum_{j=2}^{M} {\alpha_{j}} + S_{N}F_{M}$$

입니다.