[BOJ/Gold 4] 백준 25826 2차원 배열 다중 업데이트 단일 합(C++)

문제 링크

https://www.acmicpc.net/problem/25826

25826번: 2차원 배열 다중 업데이트 단일 합

 

문제

크기가 n x n인 정수형 2차원 배열 A가 주어진다. 배열 A의 원소는 A[0][0], A[0][1], …, A[n - 1][n - 1]이다. 배열 A의 모든 원소의 초깃값은 입력으로 주어진다. 배열 A에 대한 m개의 질의가 저장된 배열 B가 주어진다. 배열 B에 저장된 m개의 질의는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1을 나타내고 두 번째가 유형 2를 나타낸다.

• 1 i1 j1 i2 j2 k : 행 번호 i가 i1 ≤ i ≤ i2이고, 열 번호 j가 j1 ≤ j ≤ j2인 A[i][j]에 k를 더한다.
• 2 i1 j1 i2 j2 : 행 번호 i가 i1 ≤ i ≤ i2이고, 열 번호 j가 j1 ≤ j ≤ j2인 A[i][j]의 합을 출력한다.

배열 B에 저장된 첫 번째 질의부터 m번째 질의까지 순서대로 처리하면서 유형 2에 대한 결과를 출력하자. 단, 배열 B에는 유형 2의 질의가 마지막에 1개만 저장되어 있다.

입력

첫 번째 줄에 n과 m이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄부터 n개의 줄에 배열 A의 원소가 주어진다. i번째 줄의 j번째 수는 배열 A의 (i - 1)번째 행 (j - 1)번째 열의 원소 A[i - 1][j - 1]을 나타낸다.

다음 줄부터 m개의 줄에 걸쳐서 배열 B에 저장된 m개의 질의가 순서대로 주어진다. 한 줄에 하나의 질의를 나타내는 수가 공백을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 유형 2의 질의 결과를 출력한다.

제한

• 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 300,000
• 1 ≤ A[i][j] ≤ 1,000,000 (0 ≤ i, j ≤ n - 1)
• 배열 B에 저장된 질의는 유형 1과 유형 2만 존재한다.
• 배열 B에는 유형 2의 질의가 마지막에 1개만 저장되어 있다.
• 0 ≤ i1 ≤ i2 ≤ n - 1
• 0 ≤ j1 ≤ j2 ≤ n - 1
• 1 ≤ k ≤ 10,000

예제 입력 1

4 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 0 0 1 1 1
1 0 0 2 2 2
2 0 0 2 2

예제 출력 1

31

배열 B에 저장된 첫 번째 질의를 처리한 후 배열 A에 저장된 값은 다음과 같다.

2 2 1 1
2 2 1 1
1 1 1 1
1 1 1 1

배열 B에 저장된 두 번째 질의를 처리한 후 배열 A에 저장된 값은 다음과 같다.

4 4 3 1
4 4 3 1
3 3 3 1
1 1 1 1

배열 B에 저장된 세 번째 질의는 A[0][0]+A[0][1]+A[0][2]+A[1][0]+A[1][1]+A[1][2]+A[2][0]+A[2][1]+A[2][2]에 대한 출력을 나타낸다.

알고리즘 분류

• 누적 합

풀이

2차원 배열에서 특정 구간의 숫자에 대한 변화량을 기록하는 방법은 다음과 같다.

구간을 입력받으면, DP[I1][J1]과 DP[I2 + 1][J2 + 1]를 1 증가시키고 DP[I2 + 1][J1]과 DP[I1][J2 + 1]를 1 감소시킨다.

유형 1 질의를 다 입력받은 후 마지막으로 유형 2 질의를 입력받기 전에 모든 행에 대한 스위핑, 모든 열에 대한 스위핑을 수행한다. 그 결과는 해당 칸에 더할 수치가 된다. 이 결과의 누적 합 Sum을 구한다.

그리고 원래 배열 A 역시 누적 합을 구한 후, Sum과 더해준다.

그러면 유형 1 질의를 모두 입력받은 후 변화된 2차원 배열의 누적 합을 구할 수 있다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1001
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, C, I1, J1, I2, J2;
LL K;
LL A[MAX][MAX];
LL DP[MAX][MAX];
LL Sum[MAX][MAX];

void settings() {
    DP[I1][J1] += K;
    DP[I2 + 1][J1] -= K;
    DP[I1][J2 + 1] -= K;
    DP[I2 + 1][J2 + 1] += K;
}

void find_Answer() {
    cout << A[I2][J2] - A[I1 - 1][J2] - A[I2][J1 - 1] + A[I1 - 1][J1 - 1] << "\n";
}

void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> K;
            A[i][j] = A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1] + K;
        }
    }
    while (M--) {
        cin >> C;
        if (C == 1) {
            cin >> I1 >> J1 >> I2 >> J2 >> K;
            I1++;
            J1++;
            I2++;
            J2++;
            settings();
        }
        else if (C == 2) {
            for (int i = 1; i <= N; i++) {
                for (int j = 2; j <= N; j++) {
                    DP[i][j] = DP[i][j - 1] + DP[i][j];
                }
            }
            for (int j = 1; j <= N; j++) {
                for (int i = 2; i <= N; i++) {
                    DP[i][j] = DP[i - 1][j] + DP[i][j];
                }
            }
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + DP[i][j];
                    A[i][j] += Sum[i][j];
                }
            }
            cin >> I1 >> J1 >> I2 >> J2;
            I1++;
            J1++;
            I2++;
            J2++;
            find_Answer();
        }
    };
}

int main() {
    FASTIO
    input();

    return 0;
}