백준 25978 - 2차원 배열 다중 업데이트 다중 합 (C++)

문제

• 문제 링크

  
   BOJ 25978 - 2차원 배열 다중 업데이트 다중 합 
  

• 문제 요약

$n*n$ 크기의 행렬과, 두가지 유형으로 이루어진 $m$개의 쿼리가 주어진다.
유형 $2$의 쿼리가 주어질 때마다 그 결과를 출력해보자.

• 제한

TL : $3$ sec, ML : $512$ MB




$1 ≤ n ≤ 1,000$

$1 ≤ k ≤ 10,000$

$1 ≤ m ≤ 300,000$

$1 ≤ n_{ij} ≤ 1,000,000$

모든 유형 $1$의 질의가 유형 $2$의 질의보다 앞부분에 저장되어 있다.

알고리즘 분류

• 누적 합

풀이

"모든 유형 $1$의 질의가 유형 $2$의 질의보다 앞부분에 저장되어 있다."

위 조건이 없었다면 $2D$ $Segment$ $Tree$ $+$ $Lazy$ $Propagation$을 박아야 하나$?$ 싶을 수 있지만, 출력 요청 쿼리가 모든 업데이트 뒤에서야 등장한다.

이로 인해 $imos$법 사용을 고려해볼 수 있게 된다.

위 테크닉 또는 $2$차원 상의 누적 합을 다루는 것에 익숙치 않다면, 다음 두 문제정도 선행해보는 것을 추천한다.

BOJ 11660 - 구간 합 구하기 5

BOJ 19951 - 태상이의 훈련소 생활

---

$1$차원에서, 구간 $[x, y]$에 업데이트를 진행해야 한다면 $cnt[x]$에 $+$를, $cnt[y + 1]$에 $-$를 더해주고 최종적으로 스위핑해주어 결과를 얻을 수 있었다.

$2$차원은 결국 $1$차원의 확장이다.
임의의 업데이트에 대해 영향 받는 포인트들을 어디에 찍어야 할지 생각해보자.
앞서 언급한 두 문제를 적절히 섞어주면 된다.

구체적으로, $Q$_$[1, y1, x1, y2, x2, k]$에 대해

$cnt[y1][x1], cnt[y2 + 1][x2 + 1]$에 $+k$를,

$cnt[y1][x2 + 1], cnt[y2 + 1][x1]$에 $-k$를 더해주자.

이후 첫번째 유형 $2$ 쿼리를 마주한 순간 위에서 아래로, 왼 쪽에서 오른 쪽으로 스위핑 해 업데이트를 끝낸 후 쿼리 당 $O(1)$로 응답할 수 있다.

직사각형 단위로 잘라보면 식을 정리할 수 있는데, 자세한 내용은 아래 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
long long sum[1005][1005], cnt[1005][1005];
 
void f(int n)
{
    for (int i(1); i <= n; i++)
        for (int j(1); j <= n; j++)
        {
            cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + cnt[i][j];
        }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i(1); i <= n; i++)
        for (int j(1); j <= n; cin >> sum[i][j++]);
 
    for (int flag{}; m--;)
    {
        int o, y1, x1, y2, x2, k;
        cin >> o >> y1 >> x1 >> y2 >> x2;
        y1++, x1++, y2++, x2++;
        if (o & 1)
        {
            cin >> k;
            cnt[y1][x1] += k, cnt[y2 + 1][x2 + 1] += k;
            cnt[y1][x2 + 1] -= k, cnt[y2 + 1][x1] -= k;
        }
        else
        {
            if (!flag)
                flag = 1, f(n);
            cout << sum[y2][x2] - sum[y2][x1 - 1] - sum[y1 - 1][x2] + sum[y1 - 1][x1 - 1] << '\n';
        }
    }
}

comment

끝