32962번 - 폭우 (Hard)
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 18 | 4 | 3 | 75.000% |
문제
일렬로 놓인 $N$개의 칸에 끊임없는 비가 내린다. $i$번째 칸에는 초기에 높이 $A_i$의 벽이 세워져 있다. 벽 안에 고인 비가 가득 차면 왼쪽 끝과 오른쪽 끝의 공허로 넘쳐서 사라진다. 또한, 빗물은 일렬로 놓인 좌우 방향 이외의 방향으로 이동하지 않는다.
$Q$개의 쿼리가 주어진다. 각 쿼리는 $l, r, x$로 이뤄지며, $[l, r]$ 구간의 칸에 세워진 벽의 높이가 이후로 $x$가 된다는 의미이다.
각 쿼리가 끝날 때마다 최대 얼마만큼의 비가 고이게 될 수 있는지 답하라.
입력
첫 번째 줄에 $N$, $Q$가 차례대로 주어진다. ($1 \le N \le 100\,000; 1 \le Q \le 100\,000$)
두 번째 줄에 초기 높이 $A_i$가 순서대로 주어진다. ($1 \le A_i \le 10^9$)
세 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄마다 쿼리를 의미하는 세 정수 $l, r, x$가 공백으로 구분되어 주어진다. ($1 \le l \le r \le N; 1 \le x \le 10^9$)
입력으로 주어지는 모든 수는 정수이다.
출력
$Q$개의 줄에 걸쳐 각 쿼리를 수행했을 때의 답을 출력한다.
예제 입력 1
12 3 3 1 4 1 5 9 2 6 5 3 5 10 4 4 2 1 2 10 3 11 9
예제 출력 1
28 49 9
초기 상태는 다음과 같으며, $29$만큼의 물이 차있다.
#
#.....#
#.....#
#.....#
#.#...#
##.##.##
#.##.##.##
#.#.##.#####
#.#.########
############
$1$번 쿼리가 끝난 직후, 다음과 같이 $4$번째 칸에 세워진 벽의 높이가 $1$에서 $2$가 되어 $28$만큼의 물이 차있게 된다.
#
#.....#
#.....#
#.....#
#.#...#
##.##.##
#.##.##.##
#.#.##.#####
#.##########
############
$2$번 쿼리가 끝난 직후, 다음과 같이 $1$번째 칸과 $2$번째 칸에 세워진 벽의 높이가 $10$이 되어 $49$만큼의 물이 차있게 된다.
##.........#
##...#.....#
##...#.....#
##...#.....#
##...#.#...#
##..##.##.##
###.##.##.##
###.##.#####
############
############
$3$번 쿼리가 끝난 직후, 다음과 같이 $3$번째 칸부터 $11$번째 칸까지에 세워진 벽의 높이가 $9$가 되어 $9$만큼의 물이 차있게 된다.
##.........#
############
############
############
############
############
############
############
############
############