문제
지안지아는 똑같은 크기의 벽돌을 쌓아서 벽을 만들고 있다.
이 벽은 n열의 벽돌로 되어 있는데, 각 열은 왼쪽부터 오른쪽으로 차례대로 0부터 n − 1까지 번호가 매겨져 있다.
각 열의 높이는 서로 다를 수 있다.
열의 높이는 이 열에 쌓인 벽돌의 수이다.
지안지아는 다음과 같이 벽을 만든다.
처음에는 어느 열에도 벽돌이 없다.
다음, 지안지아는 k단계에 걸쳐 벽돌을 더하거나 또는 빼거나 한다.
k단계가 다 끝나면 벽을 다 쌓은 것이다.
매 단계마다 지안지아는 연속된 벽돌 열의 범위와 높이 h를 받고, 다음과 같은 절차에 따라 정해진 일을 한다.
- 벽돌을 더하는 단계에서는, 지안지아는 주어진 범위에 해당하는 열들 중 h장 미만의 벽돌이 쌓인 열들에 벽돌을 더해서 정확히 벽돌 h장이 쌓이게 한다. h장 이상 벽돌이 있는 열에는 아무 일도 하지 않는다.
- 벽돌을 빼는 단계에는, 지안지아는 주어진 범위에 해당하는 열들 중 h장 초과의 벽돌이 쌓인 열들에서 벽돌을 빼서 정확히 벽돌 h장이 쌓이게 한다. h장 이하 벽돌이 있는 열에는 아무 일도 하지 않는다.
당신이 할 일은 벽의 최종 모양을 결정하는 것이다.
입력
1번 줄 : n k
2번 ~ k + 1번 줄 : opi, li, ri, hi
n : 벽에 있는 열의 수
k : 단계의 수
op : 크기가 k인 배열로, 0 ≤ i ≤ k - 1일 때 opi는 단계 i에서 하는 일을 나타낸다. 이 값이 1이면 더하는 단계이고 2이면 빼는 단계이다.
l, r : 크기 k인 배열로, 0 ≤ i ≤ k − 1일 때 단계 i에 해당하는 열의 범위는 l[i] 열에서 시작하고 r[i] 열에서 끝난다. (양 끝점 l[i]와 r[i]가 포함된다.) 항상 l[i] ≤ r[i]이다.
h: 크기 k인 배열로, 0 ≤ i ≤ k − 1일 때 h[i]는 단계 i에서 주어지는 높이 파라미터이다.
- 1 ≤ n ≤ 2 000 000
- 1 ≤ k ≤ 500 000
출력
i번째 줄에는 모든 단계를 수행한 다음 열 i에 벽돌이 몇 장 있는지 출력한다.
예제
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
3
4
5
4
3
3
0
0
1
0
로그인해야 코드를 작성할 수 있어요.