[C++] 백준 6218번 Balanced Lineup

문제 링크

6218번: Balanced Lineup

문제 요약

구간의 최댓값과 최솟값의 차를 구하는 쿼리를 구현해야 한다.

접근 방법

전형적인 최대, 최소 세그먼트 트리였습니다. 최대, 최소 쿼리를 위한 함수를 두개 구현하는 대신에 함수 포인터를 이용해서 풀었습니다.

1 + 1 행사가 진행중인 문제입니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

vector<int> v, tree1, tree2;

int compare1(const int& a, const int& b) { return (a < b ? a : b); }
int compare2(const int& a, const int& b) { return (a > b ? a : b); }

void init(vector<int>& tree, int node, int start, int end, int (*compare)(const int&, const int&))
{
	if (start == end)
	{
		tree[node] = v[start];
		return;
	}

	init(tree, node * 2, start, (start + end) / 2, compare);
	init(tree, node * 2 + 1, (start + end) / 2 + 1, end, compare);
	tree[node] = compare(tree[node * 2], tree[node * 2 + 1]);
}

int query(vector<int>& tree, int node, int start, int end, int left, int right, int (*compare)(const int&, const int&))
{
	if (left > end || right < start)
		return 0;
	if (left <= start && right >= end)
		return tree[node];

	int num1 = query(tree, node * 2, start, (start + end) / 2, left, right, compare);
	int num2 = query(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right, compare);

	if (!num1) return num2;
	if (!num2) return num1;

	return compare(num1, num2);
}

int main(void)
{
	FASTIO;

	int n, q;
	cin >> n >> q;

	v.resize(n + 1);
	int treeSize = ceil(log2(n + 1)) + 1;
	tree1.resize(1 << treeSize);
	tree2.resize(1 << treeSize);

	for (int i = 1; i <= n; i++)
		cin >> v[i];

	init(tree1, 1, 1, n, compare1);
	init(tree2, 1, 1, n, compare2);

	while (q--)
	{
		int a, b;
		cin >> a >> b;
		int num1 = query(tree1, 1, 1, n, a, b, compare1);
		int num2 = query(tree2, 1, 1, n, a, b, compare2);
		cout << num2 - num1 << endl;
	}

	return 0;
}