오늘 뭐했지

https://boj.ma/33543/t

문제 요약은

\[
\sum_{i=1}^{N} \max\Bigl( A_i + \text{A증가량}, \; B_i + \text{B증가량} \Bigr)
\]
를 쿼리마다 구하는 문제입니다.

당연히 일일히 업데이트 치고, 매번 합을 구하게 되면 시간초과입니다.

$\max(x, y)$ 를 생각해봅시다. $\max(x, y)$ 는  $\max(x, y) = y + \max(x - y, 0)$ 로 나타낼 수 있습니다.

따라서 우리가 구하려는 $ \max( A_i + \text{A증가량}, \; B_i + \text{B증가량})$ 를 바꾸면,

$\max(A_i + \text{A증가량}, B_i + \text{B증가량}) = B_i + \text{B증가량} + \max((A_i + \text{A증가량}) - (B_i + \text{B증가량}), 0)$ 가 됩니다.

따라서 원래 수식을 아래와 같이 나타낼 수 있습니다.

\[\sum_{i=1}^{N} (B_i + \text{B증가량}) + \sum_{i=1}^{N} \max((A_i - B_i) + \text{A증가량 - B증가량}, 0)\]

앞쪽 식은 초기 B배열의 전체 합과 쿼리마다 B를 업데이트 칠 때마다 B증가량에 더해주면 $O(1)$에 구할 수 있습니다.

뒤쪽 식은 $(A_i - B_i)$ 를 미리 계산해둔 배열을 만들어두고, 정렬후 누적합 배열을 만들어 줍니다.

이후 각 쿼리마다 A증가량 - B증가량은 $O(1)$ 에 업데이트 하고, $ \sum_{i=1}^{N} \max((A_i - B_i) + \text{A증가량 - B증가량}, 0) $ 을 이분탐색으로 빠르게 구해줍니다.

$ A_i - B_i $ 배열을 정렬하고 누적합을 구해놓는다고 했습니다. 순서가 원래 배열의 순서에서 깨지더라도 상관없습니다.

합은 어차피 $A_i - B_i + \text{A증가량 - B증가량}$ 이 0보다 큰것들만 더해지기 때문에 0보다 큰게 몇개인지만 관심가지면 됩니다.

따라서  $(A_i - B_i) + \text{A증가량 - B증가량}  \geq 0$ 가 되는 $i$를 이분탐색으로 빠르게 찾고, 

$ N - i $ 개 원소에 대해 $ A_i - B_i + \text{A증가량 - B증가량} $ 의 합은  

$$ \text{psum}[N] - \text{psum}[\text{idx}] + \text{(A증가량 - B증가량)}  \times (N - \text{idx}) $$  

으로 나타낼 수 있습니다.

최종 수식은 아래와 같습니다.

\[
\text{sumB} + n \times \text{B증가량} + \left[ (\text{ psum }[n] - \text{ psum }[\text{idx}]) + \text{ (A증가량 - B증가량) } \times (n - \text{idx}) \right]
\]

이제 수식대로 구현해주면 됩니다.

코드는 생략합니다.

 $\max(x, y) = y + \max(x - y, 0)$ 아이디어가 중요한것 같습니다.