백준 - 히스토그램 (1725) [C++]

이 문제는 세그먼트 트리를 이용해서 풀었다.

 

시간 제한이 0.7초이므로 약 7,000만번의 연산 안으로 문제를 해결해야 한다. 특정 구간에서의 직사각형 넓이의 최댓값을 구하는 문제로, 세그먼트 트리가 떠올랐다.

 

처음에는 단순히 세그먼트 트리에 특정 구간의 직사각형 넓이 최댓값을 바로 집어넣었다. 그러나 이런식으로는 풀리지 않는데, 절반씩 구간이 잘리는 형태에서 왼쪽과 오른쪽을 부분적으로 포함하는 범위에서 최댓값이 존재할 수 있기 때문이다.

 

그래서 세그먼트 트리에는 특정 구간에서의 최소 높이를 가진 인덱스를 저장하고, 이 인덱스로 좌우를 나누는 것이 정답을 맞출 수 있는 포인트이다. 

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>
#include <algorithm>
#include <stack>
using namespace std;

#define MAX 100000
#define INF 1000000001

int arr[MAX + 1];
int segment[MAX * 4 + 1];
int N;

int init(int start, int end, int node) {
	if (start == end) {
		return segment[node] = start;
	}

	int mid = (start + end) / 2;

	int index1 = init(start, mid, node * 2);
	int index2 = init(mid + 1, end, node * 2 + 1);

	if (arr[index1] > arr[index2]) {
		segment[node] = index2;
	} else {
		segment[node] = index1;
	}

	return segment[node];
}

int findMin(int start, int end, int node, int left, int right) {
	if (end < left || right < start) {
		return -1;
	}

	if (left <= start && end <= right) {
		return segment[node];
	}

	int mid = (start + end) / 2;

	int index1 = findMin(start, mid, node * 2, left, right);
	int index2 = findMin(mid + 1, end, node * 2 + 1, left, right);

	if (index1 == -1 && index2 == -1) {
		return -1;
	} else if (index1 != -1 && index2 == -1) {
		return index1;
	} else if (index1 == -1 && index2 != -1) {
		return index2;
	} else {
		if (arr[index1] > arr[index2]) {
			return index2;
		} else {
			return index1;
		}
	}
}

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

int func(int start, int end) {
	if (start > end) {
		return -1;
	}

	int width = end - start + 1;

	int minIndex = findMin(1, N, 1, start, end);
	int height = arr[minIndex];
	int present = height * width;

	int maxVal = max(present,
		max(func(start, minIndex - 1), func(minIndex + 1, end))
	);

	return maxVal;
}

int solve() {
	init(1, N, 1);
	return func(1, N);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	input();

	cout << solve() << '\n';

	return 0;
}