[codeforces] 1906F. Maximize The Value

문제 링크
크기가 $N$인 배열 $A$가 있습니다. 처음에는 모든 $i$에 대하여 $A_{i} = 0$입니다.

그리고 배열에 적용할 $M$개의 연산이 주어집니다. $\langle L_{i}, R_{i}, X_{i} \rangle$ 형태로 주어지며 이는 $L_{i} \leq j \leq R_{i}$인 모든 $j$에 대하여 $A_{j}$를 $X_{i}$만큼 증가시킵니다.

마지막으로 $Q$개의 독립적인 쿼리가 주어집니다. $\langle K, S, T \rangle$ 형태로 주어지며 이는 $S \leq l \leq r \leq T$인 $l, r$을 골라 $A$에 $l$번째 부터 $r$번째 연산을 순서대로 적용시켜 얻을 수 있는 $A_{K}$의 최댓값을 반환합니다. 저희는 이 쿼리를 수행하는 코드를 짜야합니다.

크기가 $N \times M$이고 $B_{i, j} = \begin{cases} X_{j}, & L_{j} \leq i \leq R_{j} \\ 0, & \text{otherwise} \end{cases}$ 인 2차원 배열 $B$를 생각해봅시다. 첫번째 예제에 대해서 배열 $B$를 만들면 아래와 같습니다.

이렇게 하면 $l$번째 부터 $r$번째 연산을 순서대로 모두 적용했을 때 $A_{K} = \displaystyle\sum_{c=l}^{r}{B_{K, c}}$가 됩니다.
즉, 첫번째 예제의 첫번째 쿼리는 아래 그림의 색칠 된 부분에 포함되면서 연속적인 부분들 중 그 합이 최대인 값을 찾아주면 됩니다.

최대가 되는 경우는 아래와 같습니다.

이렇게 하면 누적합을 사용해서 처리할 수 있기 때문에 시간복잡도와 공간복잡도 모두 $O(NM + Q)$이 됩니다. $N$과 $M$은 최대 10만이므로 이 방법은 사용할 수 없습니다.
그럼 어떻게 시간복잡도와 공간복잡도를 줄여야할까요? 여기서 두가지 사실에 주목해봅시다.

• $B$의 각 열을 위에서부터 아래로 순서대로 따라가면 값은 최대 2번 바뀝니다.
• $A_{K}$는 $B$의 $K$번째 행에만 의존합니다.

즉, 1차원 배열을 만들어서 $B$의 첫번째 행으로 초기화 해준 뒤, 아래로 스위핑하면서 1차원 배열을 갱신해 가며 각 쿼리의 값을 구할 수 있습니다. 각 쿼리들은 오프라인으로 $K$의 값이 작은 순서대로 처리하면 되고 1차원 배열의 갱신과 각 쿼리의 값은 세그먼트 트리를 사용해서 처리할 수 있습니다.

시간복잡도는 $O(Q\log{Q}+M\log{M})$, 공간복잡도는 $O(Q+M)$으로 AC를 받을 수 있습니다.