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

오늘은 세그 미는날~~

평범한 최솟값 세그가 아니여서 좀 고생했다.

 

www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

이 문제의 핵심은

세그트리가 반환해주는 값이 구간 내의 히스토그램 값의 최솟값 이 아니라,

히스토그램이 최솟값을 가지는 곳의 인덱스값이다.

 

이를 위해 세그트리를 살짝 수정해 준 뒤에,

구간에서의 최대값을 찾을때에는 분할정복을 이용해주었다.

 

분할을 할때는 반드시 딱 절반에서 나누는 것이 아니라,

구간 내에서의 최솟값을 찾아서

최솟값 인덱스+1 ~ 끝

시작 ~ 최솟값 인덱스-1

이렇게 비교해주면 AC를 받을 수 있다.

 

이 구간 내에서의 최솟값을 빨리 찾기 위해 세그멘트 트리를 사용해주었다.

 

#include <bits/stdc++.h>
#define INF 123456789123456789LL
using namespace std;
typedef long long int ll;

ll arr[123456] = {0};
ll seg[456789] = {0};
int n;

int init(int node=1, int start=1, int end=n){
	if(start == end) return seg[node] = start;
	
	int mid = (start + end) / 2;
	int a = init(node*2,   start, mid);
	int b = init(node*2+1, mid+1, end);
	return seg[node] = arr[a]<=arr[b] ? a:b;
}

int query(int l, int r, int node=1, int start=1, int end=n){
	if(r < start || l > end) return 0;
	if(l <= start && end <= r) return seg[node];
	
	int mid = (start + end) / 2;
	int a = query(l, r, node*2,   start, mid);
	int b = query(l, r, node*2+1, mid+1, end);
	return arr[a] <= arr[b] ? a:b;
}

ll search(int s, int e){
	if(s==e) return arr[s];
	
	int idx = query(s,e);
	ll ret = (ll)arr[idx] * (e-s+1);
	
	if(idx > s){ ret = max(ret, search(s,idx-1)); }
	if(idx < e){ ret = max(ret, search(idx+1,e)); }
	return ret;
}

int main(){
	arr[0] = INF;
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
	init();
	
	printf("%lld\n", search(1,n));
	return 0;
}

 

 

여담으로,

위 문제의 살짝 변형된 버전의 문제가 존재하므로

빨리 가서 날먹하고 오도록 하자

www.acmicpc.net/problem/1725

1725번: 히스토그램