BOJ 25826 C++

문제접근

BOJ 19951 C++의 2차원배열 버전입니다.
같은 크기의 배열을 하나 더 만듭니다.
1 0 0 1 1 1
첫번째 쿼리입니다.

그렇다면 배열을 이렇게 초기화 해줍니다.

{
    {1 0 -1 0}
    {0 0 0 0}
    {-1 0 1 0}
    {0 0 0 0}
}

다음과 같은 과정을 실행합니다.
이중포문으로 i,j를 초기화 합니다.

for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			com[i][j] += com[i][j - 1];

이렇게 하면 배열을 다음과 같은 형태로 변합니다.

{
    {1 1 0 0}
    {0 0 0 0}
    {-1 -1 0 0}
    {0 0 0 0}
}

그다음 이중포문으로 j,i로 초기화 합니다.

{
    {1 1 0 0}
    {1 1 0 0}
    {0 0 0 0}
    {0 0 0 0}
}

이런식으로 초기화를 하면 빠른시간안에 쿼리가 저장된 배열을 얻을 수 있습니다.
그다음 이배열을 원래의 배열에 더합니다.
결과:
2 2 1 1
2 2 1 1
1 1 1 1
1 1 1 1
이과정을 한번에 실행하고 누적합을 이용해 답을 출력합니다.

코드

280ms코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m; cin >> n >> m;
	vector<vector<ll>> v(n + 2, vector<ll>(n + 2, 0));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
		}
	}
	vector<vector<ll>> com(n + 2, vector<ll>(n + 2, 0));
	for (int i = 0; i < m - 1; i++)
	{
		int tmp; cin >> tmp;
		int i1, j1, i2, j2;
		ll k; cin >> i1 >> j1 >> i2 >> j2 >> k;
		i1++; //좌표맞추기
		j1++;
		i2++;
		j2++;
		com[i1][j1] += k; //설명한 부분
		com[i1][j2 + 1] -= k;
		com[i2 + 1][j1] -= k;
		com[i2 + 1][j2 + 1] += k;
	}
	for (int i = 1; i <= n; i++) //누적합
		for (int j = 1; j <= n; j++)
			com[i][j] += com[i][j - 1];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			com[j][i] += com[j - 1][i];
	for (int i = 1; i <= n; i++) //본배열에 할당
	{
		for (int j = 1; j <= n; j++)
		{
			v[i][j] += com[i][j];
			v[i][j] = v[i][j] + (v[i - 1][j] + v[i][j - 1]) - v[i - 1][j - 1];
		}

	}
	int tmp;
	int i1, j1, i2, j2; cin >> tmp >> i1 >> j1 >> i2 >> j2;
	i1++;
	j1++;
	i2++;
	j2++;
	cout << v[i2][j2] - v[i1 - 1][j2] - v[i2][j1 - 1] + v[i1 - 1][j1 - 1];

	return 0;
}

맞았으나 오래걸린 코드

2308ms코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m; cin >> n >> m;
	vector<vector<ll>> v(n + 2, vector<ll>(n + 2, 0));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
		}
	}
	vector<vector<ll>> com(n + 2, vector<ll>(n + 2, 0));
	for (int i = 0; i < m - 1; i++)
	{
		int tmp; cin >> tmp;
		int i1, j1, i2, j2;
		ll k; cin >> i1 >> j1 >> i2 >> j2 >> k;
		int tmp1 = i1;
		while (i1 != i2 + 1) //다른방법으로 하였다.
		{
			com[i1+1][j1+1] += k;
			com[i1+1][j2 + 2] -= k;
			i1++;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			com[i][j]+= com[i][j - 1];
			v[i][j] += com[i][j];
			v[i][j] = v[i][j] + (v[i - 1][j] + v[i][j - 1]) - v[i - 1][j - 1];
		}
	}
	int tmp;
	int i1, j1, i2, j2; cin >> tmp >> i1 >> j1 >> i2 >> j2;
	i1++;
	j1++;
	i2++;
	j2++;
	cout << v[i2][j2] - v[i1 - 1][j2] - v[i2][j1 - 1] + v[i1 - 1][j1 - 1];

    return 0;
}