백준 6549 히스토그램에서 가장 큰 직사각형 C++

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

!https://www.acmicpc.net/upload/images/histogram.png

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

풀이

분할 정복을 이용하여 풀이한다.

구간의 최소값은 세그먼트 트리를 이용하여 구한다. 

 

참고

https://www.acmicpc.net/blog/view/12

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
void init(vector<int> &a, vector<int> &tree, int node, int start, int end) {
	if (start == end) {
		tree[node] = start;
	}
	else {
		init(a, tree, node * 2, start, (start + end) / 2);
		init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end);
		if (a[tree[node * 2]] <= a[tree[node * 2 + 1]]) {
			tree[node] = tree[node * 2];
		}
		else {
			tree[node] = tree[node * 2 + 1];
		}
	}
}
int query(vector<int> &a, vector<int> &tree, int node, int start, int end, int i, int j) {
	if (i > end || j < start) {
		return -1;
	}
	if (i <= start && end <= j) {
		return tree[node];
	}
	int m1 = query(a, tree, 2 * node, start, (start + end) / 2, i, j);
	int m2 = query(a, tree, 2 * node + 1, (start + end) / 2 + 1, end, i, j);
	if (m1 == -1) {
		return m2;
	}
	else if (m2 == -1) {
		return m1;
	}
	else {
		if (a[m1] <= a[m2]) {
			return m1;
		}
		else {
			return m2;
		}
	}
}
long long largest(vector<int> &a, vector<int> &tree, int start, int end) {
	int n = a.size();
	int m = query(a, tree, 1, 0, n - 1, start, end);
	long long area = (long long)(end - start + 1)*(long long)a[m];
	if (start <= m - 1) {
		long long temp = largest(a, tree, start, m - 1);
		if (area < temp) {
			area = temp;
		}
	}
	if (m + 1 <= end) {
		long long temp = largest(a, tree, m + 1, end);
		if (area < temp) {
			area = temp;
		}
	}
	return area;
}
int main() {

	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int h = (int)(ceil(log2(n)) + 1e-9);
		int tree_size = (1 << (h + 1));
		vector<int> tree(tree_size);
		init(a, tree, 1, 0, n - 1);
		cout << largest(a, tree, 0, n - 1) << '\n';
	}
	return 0;
}