백준 2357 c++ "최솟값과 최댓값" -PlusUltraCode-

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

 

[필자 사고]

이 문제를 처음 봤을 때 부르스트 알고리즘을 적용하려 했지만 범위를 보고 그만두었다.

다음으로 누적합을 이용하면 뭐 달라질까?? 생각했지만 에초에 최솟값과 최댓값이라 상관이 없었따.

처음으로 배운 세그먼트트리를 이용해야 된다.

 

세그먼트 트리는 초기값을 잘 설정하면 그 이후부터는 쉽게 풀 수 있따.

시간복잡도가 logN 이라 시간내에 풀 수 있다.

아래는 코드 해설이다.

[코드 해설]

 

• Input 함수
  • 배열 크기(N)와 질의 수(M)를 입력받습니다.
  • 배열 arr를 초기화하고, 데이터를 입력받아 저장합니다.
• Init_Segment_Tree 함수
  • 세그먼트 트리를 초기화합니다:
    • treeHeight: 배열의 크기(N)에 대한 로그 값으로 세그먼트 트리의 높이를 계산합니다.
    • treeSize: 세그먼트 트리 전체의 노드 수를 계산합니다.
    • leftStartIdx: 리프 노드가 시작하는 인덱스를 계산합니다.
  • maxTree와 minTree를 각각 LONG_MIN과 LONG_MAX으로 초기화합니다.
  • 입력 배열(arr)의 값을 리프 노드에 할당합니다.
  • 부모 노드에 대해 자식 노드 값을 비교하여 maxTree와 minTree를 구성합니다.
• Query 함수
  • 주어진 구간 [start, end]에서 최대값 또는 최소값을 구합니다:
    • isMaxFlag가 true이면 maxTree를 기준으로 최대값을 계산합니다.
    • isMaxFlag가 false이면 minTree를 기준으로 최소값을 계산합니다.
  • start와 end를 리프 노드 위치로 변환한 후, 트리를 따라 올라가며 구간 값을 계산합니다:
    • start가 홀수인 경우 해당 노드 값을 결과에 반영하고 오른쪽으로 이동합니다.
    • end가 짝수인 경우 해당 노드 값을 결과에 반영하고 왼쪽으로 이동합니다.
  • 구간을 좁히며 루트 방향으로 이동합니다.
• Game_Start 함수
  • Init_Segment_Tree를 호출하여 세그먼트 트리를 초기화합니다.
  • 각 질의에 대해 시작점(start)과 끝점(end)을 입력받습니다:
    • start와 end의 순서를 정리하여 항상 작은 값부터 큰 값으로 설정합니다.
  • Query 함수를 호출하여 해당 구간의 최소값과 최대값을 계산합니다.
  • 결과를 출력합니다.
• main 함수
  • main 함수는 Input 함수로 데이터를 입력받고, Game_Start 함수로 게임을 실행합니다.
  • 입출력 속도를 높이기 위해 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)를 사용합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

vector<long> maxTree;
vector<long> minTree;
vector<long> arr;

int N, M;
int treeHeight, treeSize, leftStartIdx;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
}

void Init_Segment_Tree() {
	treeHeight = (int)ceil(log2(N));
	treeSize = (1 << (treeHeight + 1));
	leftStartIdx = treeSize / 2;

	maxTree.resize(treeSize, LONG_MIN);
	minTree.resize(treeSize, LONG_MAX);

	for (int i = 0; i < N; i++) {
		maxTree[i + leftStartIdx] = arr[i];
		minTree[i + leftStartIdx] = arr[i];
	}

	for (int i = leftStartIdx - 1; i > 0; i--) {
		maxTree[i] = max(maxTree[i * 2], maxTree[i * 2 + 1]);
		minTree[i] = min(minTree[i * 2], minTree[i * 2 + 1]);
	}
}
long Query(vector<long> & tree,int start, int end, bool isMaxFlag) {
	
	start += leftStartIdx;
	end += leftStartIdx;

	long result = isMaxFlag ? LONG_MIN : LONG_MAX;


	while (start <= end) {
		if (start % 2 == 1) {
			result = isMaxFlag ? max(result, maxTree[start]) : min(result, minTree[start]);
			start++;
		}
		if (end % 2 == 0) {
			result = isMaxFlag ? max(result, maxTree[end]) : min(result, minTree[end]);
			end--;
		}

		start /= 2;
		end /= 2;
	}
	
	return result;
}


void Game_Start() {
	Init_Segment_Tree();

	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		start = min(start, end);
		end = max(start, end);

		long minValue = Query(minTree, start - 1, end - 1, false);
		long maxValue = Query(maxTree, start - 1, end - 1, true);

		cout << minValue << " " << maxValue << '\n';

	}
}

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

	Input();
	Game_Start();
}