[자료구조] 백준 6218번: Balanced Lineup (C++)

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

6218번: Balanced Lineup

최댓값 세그 트리랑 최솟값 세그 트리를 구현하고, 쿼리마다 최댓값과 최솟값을 빼주면 되는 간단한 문제였다.

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX (50000 + 1)
#define ll long long
#define INF 1000000 + 1
using namespace std;

// 1 <= height <= 1000000
int arr[MAX];
int minTree[MAX * 4];
int maxTree[MAX * 4];
int n, q;

int minInit(int start, int end, int node) {
	if (start == end) {
		return minTree[node] = arr[start];
	}
	int mid = (start + end) >> 1;
	return minTree[node] = min(minInit(start, mid, node * 2), minInit(mid + 1, end, node * 2 + 1));
}

int maxInit(int start, int end, int node) {
	if (start == end) {
		return maxTree[node] = arr[start];
	}
	int mid = (start + end) >> 1;
	return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1));
}

int maxQuery(int start, int end, int node, int left, int right) {
	if (start > right || end < left) return 0;
	if (left <= start && end <= right) {
		return maxTree[node];
	}
	int mid = (start + end) / 2;
	return max(maxQuery(start, mid, node * 2, left, right), maxQuery(mid + 1, end, node * 2 + 1, left, right));
}

int minQuery(int start, int end, int node, int left, int right) {
	if (start > right || end < left) return INF;
	if (left <= start && end <= right) {
		return minTree[node];
	}
	int mid = (start + end) / 2;
	return min(minQuery(start, mid, node * 2, left, right), minQuery(mid + 1, end, node * 2 + 1, left, right));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	minInit(1, n, 1);
	maxInit(1, n, 1);
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		cout << maxQuery(1, n, 1, a, b) - minQuery(1, n, 1, a, b) << '\n';
	}
	return 0;
}