[백준] 6549번 히스토그램에서 가장 큰 직사각형 (C++)

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

Segment Tree 자료구조를 이용해 답을 구하는 문제이다.

Segment Tree는 특정한 범위의 데이터의 합을 빠르고 간단하게 구하는 자료구조이다.

문제를 푸는 접근 방법은 다음과 같다.

1. Segment Tree를 가장 낮은 높이의 인덱스 기준으로 만들어준다.
2. 전체 부분에 대해 가장 낮은 높이의 인덱스를 구해서 구간의 넓이를 구해준다.
3. index의 left, right 부분에 대해서 2번과 같은 방법으로 반복해주면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int n;

// segment tree 초기화
void init(vector<long long>& tree, vector<long long>& v, int node, int start, int end) {
	if (start == end) tree[node] = start;
	else {
		int mid = (start + end) / 2;
		init(tree, v, 2 * node, start, mid);
		init(tree, v, 2 * node + 1, mid + 1, end);
		if (v[tree[2 * node]] < v[tree[2 * node + 1]]) tree[node] = tree[2 * node];
		else tree[node] = tree[2 * node + 1];
	}
}

// 가장 작은 높이의 index 반환
int query(vector<long long>& tree, vector<long long>& v, int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) return tree[node];
	else if (right < start || end < left) return -1;

	int mid = (start + end) / 2;
	int l = query(tree, v, 2 * node, start, mid, left, right);
	int r = query(tree, v, 2 * node + 1, mid + 1, end, left, right);
	if (l == -1) return r;
	else if (r == -1) return l;
	else if (v[l] < v[r]) return l;
	else return r;
}

// 재귀를 통한 구간 합 계산
long long get_max_area(vector<long long>& tree, vector<long long>& v, int start, int end) {
	int idx = query(tree, v, 1, 1, n, start, end);
	long long area = (end - start + 1) * v[idx];
	if (idx > start) {
		long long left = get_max_area(tree, v, start, idx - 1);
		area = max(area, left);
	}
	if (idx < end) {
		long long right = get_max_area(tree, v, idx + 1, end);
		area = max(area, right);
	}
	return area;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	while (n != 0) {
		vector<long long> v(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
		}

		int height = (int)ceil(log2(n));
		int tree_size = (1 << (height + 1));
		vector<long long> tree(tree_size);
		init(tree, v, 1, 1, n);
		cout << get_max_area(tree, v, 1, n) << "\n";
		cin >> n;
	}
}