[백준-2357] 최솟값과 최댓값

전형적인 세그먼트 트리 문제이다. 일단 시간 제한이 2초이기 때문에 일일이 10만개의 정수 쌍 입력에 대해 10만개의 배열에서 최솟값과 최댓값을 뒤지게 되면 복잡도가 터지게 된다.

이를 위해 미리 답들을 트리 형태로 저장해놓는 세그먼트 트리를 사용하여 복잡도를 줄일 수 있다.

값을 저장할 때마다 최솟값과 최댓값을 log(n) 의 복잡도로 저장해놓는 식이다. 그 후 정수 쌍 입력을 받을 때마다 만들어 두었던 세그먼트 트리에 query를 날리는 식으로 문제를 풀게 되면 답이 금방 나오게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
LL max_tree[1 << 20];
LL min_tree[1 << 20];
LL min_query_seg(int node, int s, int e, int l, int r) {
	if (r < s || e < l) return 1000000000;
	if (l <= s && e <= r) return min_tree[node];
	else
		return min(min_query_seg(node * 2, s, (s + e) / 2, l, r),
			min_query_seg(node * 2 + 1, (s + e) / 2 + 1, e, l, r));
	
}
LL max_query_seg(int node, int s, int e, int l, int r) {
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return max_tree[node];
	else 
		return max(max_query_seg(node * 2, s, (s + e) / 2, l, r),
			max_query_seg(node * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
void update_seg(int node, int s, int e, int idx, int v) {
	if (idx < s || e < idx) return;
	if (s == e) {
		max_tree[node] = v;
		min_tree[node] = v;
	}
	else {
		update_seg(node * 2, s, (s + e) / 2, idx, v);
		update_seg(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
		max_tree[node] = max(max_tree[node * 2], max_tree[node * 2 + 1]);
		min_tree[node] = min(min_tree[node * 2], min_tree[node * 2 + 1]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	LL n, m;
	LL a, b;
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a);
		update_seg(1, 1, n, i, a);
	}
	pair<LL, LL> ans;
	
	for (int i = 0; i < m; i++) {
		scanf("%lld %lld", &a, &b);
		printf("%lld ", min_query_seg(1, 1, n, a, b));
		printf("%lld\n", max_query_seg(1, 1, n, a, b));
	}
	
	return 0;
}

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

2357번: 최솟값과 최댓값