백준 32322 c++ "Hotel Rooms" -PlusUltraCode-

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

[필자 사고]

기본적인 세그먼트 트리를 선언할줄 아냐 묻는 문제이다.

조심해야 될 부분은 쿼리를 묻는 부분이 항상 작은데에서 큰범위가 아닐 수도 있다는 점과

초기화 한 쿼리 N을 항상 query 나 update 의 end값에 넣어야 된다는 점이 있다.

[코드 해설]

1. 세그먼트 트리 초기화 (Init_Tree 함수)
   • Init_Tree 함수는 배열의 각 위치를 초기화하며, 모든 값을 1로 설정합니다.
   • 세그먼트 트리의 리프 노드는 배열의 각 원소를 나타내며, 내부 노드는 해당 구간의 합을 저장합니다.
   • 구간 [start, end]를 반으로 나누어 재귀적으로 초기화합니다.
   • 리프 노드: start == end일 때 트리의 해당 위치를 1로 설정합니다.
   • 내부 노드: 왼쪽과 오른쪽 자식 노드의 합을 계산하여 저장합니다.

---

1. 구간 합 계산 (Query 함수)
   • 입력된 구간 [left, right]에 대한 합을 계산합니다.
   • 현재 노드의 구간 [start, end]가 입력 구간에 완전히 포함되면 해당 노드 값을 반환합니다.
   • 현재 노드의 구간이 입력 구간과 겹치지 않으면 0을 반환합니다.
   • 구간이 겹치는 경우, 자식 노드로 이동하여 합을 계산합니다.
     이는 왼쪽 자식 (node * 2)과 오른쪽 자식 (node * 2 + 1)의 결과를 합산하여 반환합니다.

---

1. 값 갱신 (Update 함수)
   • 배열의 특정 인덱스 idx에 대해 값을 변경하고, 이에 따라 세그먼트 트리 값을 갱신합니다.
   • 현재 노드가 해당 인덱스를 포함하는 경우 값을 업데이트하고, 자식 노드로 이동하여 영향을 전파합니다.
   • 갱신된 값을 부모 노드에 반영하여 세그먼트 트리의 일관성을 유지합니다.
   • diff는 업데이트할 값의 변화량을 나타냅니다.

---

1. 게임 로직 (Game_Start 함수)
   • Game_Start 함수는 프로그램의 주요 실행 흐름을 담당합니다.
   • 입력값 초기화
     • N: 배열의 크기
     • M: 쿼리의 개수
   • 세그먼트 트리를 초기화하여 배열의 모든 값을 1로 설정합니다.
   • 쿼리 처리
     • 'A' 명령어: 구간 [a, b]의 합을 계산하고 결과를 출력합니다.
       Query 함수 호출로 해당 구간 합을 계산합니다.
     • 'R' 명령어: 특정 위치 num의 값을 감소시킵니다.
       Update 함수 호출로 해당 인덱스 값을 -1만큼 변경합니다.

---

1. 메인 함수 (main)
   • Game_Start 함수를 호출하여 입력을 처리하고 명령을 수행합니다.
   • ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)를 사용하여 입출력 속도를 최적화합니다.

[소스 코드 ]

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<long> tree;
vector<long > arr;
long ans = 0;

void Input() {
	cin >> N;
	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 sum_Tree(int node, int start, int end) {
	if (start == end) {
		return;
	}

	int mid = (start + end) / 2;
	sum_Tree(node * 2, start, mid);
	sum_Tree(node * 2 + 1, mid + 1, end);

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

void Query(int node, int start, int end, int count) {
	if (start == end) {
		ans = start;
		return;
	}

	int mid = (start + end) / 2;
	if (tree[node * 2] >= count) {
		Query(node * 2, start, mid, count);
	}
	else {
		Query(node * 2 + 1, mid + 1, end, count - tree[node * 2]);
	}
}

void Update(int node, int start, int end, int idx, int diff) {
	if (start == end) {
		tree[node] += diff;
		return;
	}

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

	tree[node] += diff;
}

void Game_Start() {
	cin >> M;

	tree.resize(N * 4 + 1,0);

	
		Init_Tree(1, 1, N);
	
	

	for (int i = 0; i < M; i++) {
		int flag;
		cin >> flag;

		if (flag == 1) {
			int idx, diff;
			cin >> idx >> diff;
			Update(1, 1, N, idx, diff);
		}
		else {
			int num;
			cin >> num;
			Query(1, 1, N, num);
			cout << ans << '\n';
		}
	}
}

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