[C++] 백준 10277번: JuQueen

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

10277번: JuQueen

 > 들어가기 전에

해당 글은 Lazy Propagated Segment Tree를 밑바탕으로 하여 작성하였다.

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-2

[Python] Lazy Propagation (백준 10999번: 구간 합 구하기 2)

 

 > 접근

예제 입력 1을 보면, 2번째 명령으로 [0 0 7 7 7 7 7 7 7 7]의 상태에서 아래 명령어를 수행하게 된다.

groupchange 0 2 10

결과적으로, [3 3 10 7 7 7 7 7 7 7]가 되어야 한다. 이 때 필요한 정보는, '0~2 구간에서의 최댓값'(=7)이다.

 

다음으로 마지막 명령어를 보자.

change 0 -5

이 명령어로 인해 값은 [0 3 10 7 7 7 7 7 7 7]가 된다. 이 때는 '0~0 구간에서의 최솟값'을 통해 -5가 아닌 -3을 업데이트해주어야 한다는 정보를 얻게 된다.

 

따라서, 세그먼트 트리에 min, max를 저장하면 된다. 세그먼트 트리를 2개를 쓰거나, pair<int, int>를 담은 세그먼트 트리를 쓰면 되는데, 후자의 방식을 택하였다.

 

 > 풀이

min, max 정보를 담은 세그먼트 트리를 구현한 뒤 제출하였는데 TLE가 나왔었다. 따라서 min-max segmen tree에 Lazy Propagation을 덧붙이기만 하면 된다.

#include <bits/stdc++.h>
using namespace std;

int C, N, O;
pair<int, int> tree[4587520*4 + 1]; // min, max
int lazy[4587520*4 + 1];

void propagateTree(int index, int start, int end) {
	if (lazy[index] != 0) {
		tree[index].first += lazy[index];
		tree[index].second += lazy[index];

		if (start != end) {
			lazy[index * 2] += lazy[index];
			lazy[index * 2 + 1] += lazy[index];
		}

		lazy[index] = 0;
	}
}

void initializeTree(int index, int start, int end) {
	if (start == end) return;
	else {
		int mid = (start + end) / 2;
		initializeTree(index * 2, start, mid);
		initializeTree(index * 2 + 1, mid + 1, end);
	}
	tree[index] = { 0, 0 };

	return;
}

void updateTree(int toAdd, int left, int right, int index, int start, int end) {
	propagateTree(index, start, end);

	if (end < left || right < start) return;

	if (left <= start && end <= right) {
		lazy[index] += toAdd;
		propagateTree(index, start, end);

		return;
	}

	int mid = (start + end) / 2;
	updateTree(toAdd, left, right, index * 2, start, mid);
	updateTree(toAdd, left, right, index * 2 + 1, mid+1, end);

	tree[index].first = min(tree[index * 2].first, tree[index * 2 + 1].first);
	tree[index].second = max(tree[index * 2].second, tree[index * 2 + 1].second);
}

pair<int, int> queryTree(int left, int right, int index, int start, int end) {
	propagateTree(index, start, end);

	if (end < left || right < start) return {10001, -10001};

	if (left <= start && end <= right) return tree[index];

	int mid = (start + end) / 2;
	pair<int, int> leftRes = queryTree(left, right, index * 2, start, mid);
	pair<int, int> rightRes = queryTree(left, right, index * 2 + 1, mid + 1, end);
	
	return { min(leftRes.first, rightRes.first), max(leftRes.second, rightRes.second) };
}

int getToAdd(pair<int, int> minMax, int toAdd) {
	int res = toAdd;
	if (minMax.first + toAdd < 0) res = -minMax.first;
	else if (minMax.second + toAdd > N) res = N - minMax.second;

	return res;
}

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

	cin >> C >> N >> O;

	initializeTree(1, 1, C);

	string operation;
	int X, A, B, S;
	for (i = 0; i < O; i++) {
		cin >> operation;
		if (operation.compare("change") == 0) {
			cin >> X >> S;
			X++;

			int toAdd = getToAdd(queryTree(X, X, 1, 1, C), S);
			updateTree(toAdd, X, X, 1, 1, C);
			cout << toAdd << "\n";
		}
		else if (operation.compare("groupchange") == 0) {
			cin >> A >> B >> S;
			A++; B++;

			int toAdd = getToAdd(queryTree(A, B, 1, 1, C), S);
			updateTree(toAdd, A, B, 1, 1, C);
			cout << toAdd << "\n";
		}
		else if (operation.compare("state") == 0) {
			cin >> X;
			X++;

			cout << queryTree(X, X, 1, 1, C).first << "\n";
		}
	}

	return 0;
}