Matrix Addition

면접 대비

시간 제한1초메모리 제한1024 MB

요약
N x N 행렬에 Q개의 직사각형 덧셈 연산을 적용한 뒤 최종 행렬을 출력한다. 2차원 차분 배열로 빠르게 처리한다.
난이도

보통10점 중 4점

유형
배열, 누적 합, 행렬, 구현
정답자
아직 제출이 없습니다

문제

You are given an N×NN \times N matrix AA initialized with arbitrary values. You will receive QQ operations, each defined by five values: R_1,C_1,R_2,C_2,VR\_1, C\_1, R\_2, C\_2, V. For each operation, you need to update the matrix by adding VV to all elements in the submatrix defined by the rows from R_1R\_1 to R_2R\_2 and the columns from C_1C\_1 to C_2C\_2.

입력

The first line contains two integers NN and QQ, the matrix size and the number of operations. (1≤N≤1,000,1≤Q≤200,000)(1 \leq N \leq 1\\,000, 1 \leq Q \leq 200\\,000)

The next NN lines each contain NN integers, forming the initial matrix AA. (0≤A_ij≤100)(0 \leq A\_{ij} \leq 100)

Each of the next QQ lines contains five integers R_1,C_1,R_2,C_2,VR\_1, C\_1, R\_2, C\_2, V, describing an operation to add VV to every element in the submatrix with rows R_1R\_1 to R_2R\_2 and columns C_1C\_1 to C_2C\_2 (1-based indices, and 1≤R_1≤R_2≤N,1≤C_1≤C_2≤N,0≤V≤100)1 \leq R\_1 \leq R\_2 \leq N, 1 \leq C\_1 \leq C\_2 \leq N, 0 \leq V \leq 100).

출력

Print the resulting matrix after performing all QQ operations: NN lines, each with NN integers separated by spaces.

예제1

  1. 예제 1

    입력
    4 2
0 0 0 5
0 0 0 0
0 0 0 0
0 0 0 0
1 1 3 2 1
2 2 4 4 2
    예상 출력
    1 1 0 5
1 3 2 2
1 3 2 2
0 2 2 2