[C++] 백준 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;
}
Author And Source
이 문제에 관하여([C++] 백준 6218번 Balanced Lineup), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beclever/C-백준-1722번-순열의-순서-nysuk0wx저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)