백준 2357번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	192MB	골드 1

사진을 클릭하면 문제로 이동합니다.

---

풀이

 세그먼트 트리 문제는 처음 다루는 것 같다. 그만큼 본인의 티어가 골드~플레 중하위일때 날로 먹기 편한 문제이기도 하고, 응용할 수 있는 부분이 매우 많아 입문은 쉬울지언정, 숙달하는데 정말 어려운 알고리즘중 하나라고 생각한다.

 

 세그먼트 트리는 배열이 있을 때, 리프노드에는 배열의 각 원소, 그러니까 구간의 길이가 1인 정보가 들어있고, 부모 노드로 향할수록, 해당 구간의 특정한 작업을 한 값(예를 들어 구간의 합, 곱, 최대최소, 그외 기타 etc...)을 저장하고, 배열에 변경이 생겨도 해당 구간의 노드들을 업데이트하는 등의 작업을 수행하기에 용이한 자료구조이다. 보통 배열의 원소나 구간을 수정하는 쿼리와, 배열의 구간에 특정 작업을 요구하는 쿼리가 같이 들어올 때, 해당 자료구조를 이용한다. 일반적으로 배열의 원소를 수정하는 것이 일반적인 세그먼트 트리이지만, 배열의 구간을 수정해야하는 경우, 레이지 프로파게이션 기법을 적용한 레이지 세그먼트 트리를 사용하는 것이 효율적이다. 물론 아직 레이지 세그먼트 트리를 제대로 공부하지 않았기에, 공부를 어느정도 마치면 할 것 같다.

 

 해당 문제는 배열을 업데이트하는 쿼리는 존재하지 않지만, 배열의 구간에 대해 반복적인 답을 요구하기 때문에, 세그먼트 트리를 적용하면 편하게 풀 수 있다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

template<class T>
class SegTree {
	size_t len, elemCnt;
	vector<T> tree;
	int (*f)(int,int);
	int err;

	T _init(int st, int ed, int cur, const vector<T>& container) {
		if (st == ed) {
			return tree[cur] = container[st - 1];
		}

		int mid = (st + ed) >> 1;

		return tree[cur] = f(_init(st, mid, cur*2, container), _init(mid + 1, ed, cur * 2 + 1, container));
	}

	T _range(int st, int ed, int cur, int left, int right) {
		if (left > ed || right < st) return err;

		if (left <= st && ed <= right) return tree[cur];

		int mid = (st + ed) >> 1;
		return f(_range(st, mid, cur * 2, left, right), _range(mid + 1, ed, cur * 2 + 1, left, right));
	}

public:
	SegTree(const vector<T>& container, int (*f)(int,int), int err) {
		this->err = err;
		this->f = f;
		elemCnt = container.size();

		len = 1UL << ((int)ceil(log2(container.size())) + 1);
		tree = vector<T>(len + 1);

		_init(1, elemCnt, 1, container);
	}

	T range(int left, int right) {
		return _range(1, elemCnt, 1, left, right);
	}
};

int n, m;
vector<int> container;
vector<pair<int,int>> query;

void input() {
	cin >> n >> m;
	container.resize(n), query.resize(m);

	for(int& x : container) cin >> x;
	for(auto& [st, ed] : query) cin >> st >> ed;
}

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

void sol() {
	SegTree seg_max(container, max, -1), seg_min(container, min, 1234567890);

	for(auto& [st, ed] : query) {
		cout << seg_min.range(st, ed) << ' ' << seg_max.range(st, ed) << endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}