백준 6213 c++ "Balanced Lineup" -PlusUltraCode-

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

[필자 사고]

이 문제는 세그먼트 트리 기본문제로 적당하다고 생각한다. 

주의할 점은 주어진 쿼리 인덱스 범위가 항상 작은거에서 큰거로 입력될거라는 것이다.

int a,b 라고 했을 때 a가 b보다 항상 작다라고 가정하면 안된다.

[코드 해설]

 

• 입력 데이터 처리 및 초기화
  • N은 배열의 크기, Q는 쿼리의 개수를 나타냅니다.
  • 배열 arr는 입력값을 저장합니다.
  • minTree와 maxTree는 각각 최소값과 최대값을 저장하는 세그먼트 트리로, 배열 크기의 4배로 초기화됩니다.
• 세그먼트 트리 초기화 (initTree 함수)
  • initTree 함수는 세그먼트 트리를 재귀적으로 초기화합니다.
  • 구간 [start, end]를 node에 할당하며, 리프 노드에서 배열의 값을 저장합니다.
  • 리프 노드가 아닌 경우, 왼쪽 (node * 2)과 오른쪽 (node * 2 + 1) 자식 노드에서 값을 가져와 최소값 또는 최대값을 계산하여 부모 노드에 저장합니다.
• 쿼리 처리 (Query 함수)
  • Query 함수는 세그먼트 트리를 활용하여 특정 구간 [left, right]의 최소값 또는 최대값을 구합니다.
  • 구간이 완전히 포함된 경우 해당 노드 값을 반환하고, 구간이 겹치지 않는 경우 최소값은 LONG_MAX, 최대값은 LONG_MIN을 반환합니다.
  • 구간이 일부 겹치는 경우, 왼쪽 자식과 오른쪽 자식에서 각각 값을 구한 뒤, 최소값 또는 최대값으로 합칩니다.
• 메인 로직 (Game_Start 함수)
  • 배열과 세그먼트 트리를 초기화합니다.
  • 각 쿼리마다 Query 함수를 호출하여 구간 [left, right]의 최대값과 최소값을 구합니다.
  • 두 값의 차이를 계산하여 출력합니다.
• 입출력 최적화
  • ios::sync_with_stdio(false)와 cin.tie(0)을 사용하여 입출력 속도를 최적화합니다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<long> tree;
vector<long> arr;
int M;

void Input() {
	cin >> N;
	tree.resize(4 * N + 1);
	arr.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void Init_Tree(int node, int start, int end) {
	if (start == end) {
		tree[node] = arr[start];
		return;
	}
	int mid = (start + end) / 2;

	Init_Tree(node * 2, start, mid);
	Init_Tree(node * 2 + 1, mid + 1, end);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void Update(int node, int start, int end, int idx, long diff) {
	if (idx < start || end < idx)return;

	if (start == end) {
		tree[node] = diff;
		return;
	}

	int mid = (start + end) / 2;
	if (idx <= start) {
		Update(node * 2, start, mid, idx, diff);
	}
	else {
		Update(node * 2 + 1, mid + 1, end, idx, diff);
	}

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long Query(int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		return tree[node];
	}

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

	int mid = (start + end) / 2;
	return Query(node * 2, start, mid, left, right) +
		Query(node * 2 + 1, mid + 1, end, left, right);
}

void Game_Start() {
	Init_Tree(1, 1, N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		char ch; int a, b;
		cin >> ch;
		cin >> a >> b;
		if (ch == 'R') {
			cout << Query(1, 1, N, a, b) << '\n';
		}
		else {
			Update(1, 1, N, a, b);
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Input();
	Game_Start();
}