백준 - 여왕벌 (10836번 - KOI)

 링크

문제를 꼼꼼히 읽어봐야 하는 문제이다.

주어지는 왼쪽, 위 배열은 항상 증가하므로 나머지 애벌레들의 크기는 맨 위 애벌레의 크기와 항상 같다는 걸 알 수 있다.

(위 애벌레의 증가율은 항상 왼쪽, 왼쪽 위 애벌레 이상이므로)

문제는 왼쪽, 위쪽 애벌레의 최종 크기를 구하는 거였는데

최대가 1400 * 100만이라 각 쿼리마다 0, 1, 2 를 카운트해주면 시간초과가 날 것 같아

lazy propagate 구간합 업데이트를 이용했다.

0, 1, 2의 개수에 대해 각각 세그먼트 트리를 만들어 해당 구간의 개수를 카운트해주고

왼쪽, 위쪽 애벌레에 더해주었다.

#include<iostream>
#include<memory.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
int mv1[4] = { 0, 0, 1, -1 };
int mv2[4] = { 1, -1, 0, 0 };
int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };

int n, m;
int dp[701][701];
int lazy[10000][3];
int tree[10000][3];

void propagate(int now, int s, int e, int num) {
	//자식 노드들에 lazy값을 전파
	if (lazy[now] != 0) {
		
		if (s != e) {
			lazy[now * 2][num] += lazy[now][num];
			lazy[now * 2 + 1][num] += lazy[now][num];
		}

		tree[now][num] += (e - s + 1) * lazy[now][num];
		lazy[now][num] = 0;
	}
}

void update(int now, int s, int e, int l, int r, int num) {
	//구간 업데이트
	propagate(now, s, e, num);

	if (r < s || l > e)	return;

	if (l <= s && r >= e) {
		lazy[now][num]++;
		propagate(now, s, e, num);
		return;
	}

	update(now * 2, s, (s + e) / 2, l, r, num);
	update(now * 2 + 1, (s + e) / 2 + 1, e, l, r, num);

	tree[now][num] = tree[now * 2][num] + tree[now * 2 + 1][num];
}

int get(int now, int s, int e, int l, int r, int num) {
	propagate(now, s, e, num);

	if (r < s || l > e)	return 0;

	if (l <= s && r >= e) {
		propagate(now, s, e, num);
		return tree[now][num];
	}

	return get(now * 2, s, (s + e) / 2, l, r, num) + get(now * 2 + 1, (s + e) / 2 + 1, e, l, r, num);
}

int main(void) {
	FIO;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int p = 0;

		for (int j = 0; j < 3; j++)
		{
			int c;
			cin >> c;

			if (c == 0)	continue;
			//개수가 0이면 업데이트할 게 없으므로 continue

			update(1, 1, 2 * n - 1, p + 1, p + c, j);
			//개수만큼 구간 업데이트

			p += c;
		}
	}

	int ptr = 1;

	for (int i = n - 1; i >= 0; i--)
	{
		dp[i][0] = 1;

		for (int j = 0; j < 3; j++)
		{
			dp[i][0] += get(1, 1, 2 * n - 1, ptr, ptr, j) * j;
			//왼쪽 애벌레 최종 크기
		}
		ptr++;
	}

	for (int i = 1; i < n; i++)
	{
		dp[0][i] = 1;

		for (int j = 0; j < 3; j++)
		{
			dp[0][i] += get(1, 1, 2 * n - 1, ptr, ptr, j) * j;
			//위쪽 애벌레 최종 크기
			
		}
		ptr++;
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < n; j++)
		{
			dp[i][j] = dp[i - 1][j];
			//나머지 애벌레의 크기 == 위 애벌레의 크기
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}
}