취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25826번 문제인 2차원 배열 다중 업데이트 단일 합이다.
문제는 아래 링크를 확인하자.

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

모든 업데이트를 전부 한 뒤 배열의 각 성분이 무엇인지를 빠르게 계산하는 방법으로 (2차원) imos법이 존재하나, 이 문제는 더욱 간단하게 해결할 수 있는 방법이 존재한다.

하나뿐인 유형2의 쿼리를 먼저 보고, 유형 2의 쿼리의 영역에 대응되는 초기 배열의 수들의 합에 각 유형1의 쿼리의 영역과 유형2의 쿼리의 영역의 겹치는 칸수만큼 k를 추가해나가는 것으로도 답을 충분히 구할 수 있다.

모든 주어진 쿼리들을 주어진 순서대로 이행하며 문제를 해결할 필요는 없다는 점을 기억하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, M;
int arr[1000][1000];
int qry[300000][5];
int rL, rR, cL, cR;
ll ans = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> arr[r][c];
		}
	}

	for (int k = 1; k < M; k++) cin >> qry[k][0] >> qry[k][0] >> qry[k][2] >> qry[k][1] >> qry[k][3] >> qry[k][4];
	cin >> rL >> rL >> cL >> rR >> cR;

	for (int r = rL; r <= rR; r++) {
		for (int c = cL; c <= cR; c++) {
			ans += arr[r][c];
		}
	}

	for (int k = 1; k < M; k++) {
		ll rrLL = max(rL, qry[k][0]), rrRR = min(rR, qry[k][1]);
		ll ccLL = max(cL, qry[k][2]), ccRR = min(cR, qry[k][3]);
		if (rrLL <= rrRR && ccLL <= ccRR) {
			ans += (rrRR - rrLL + 1) * (ccRR - ccLL + 1) * qry[k][4];
		}
	}

	cout << ans;
}