BOJ_6549_히스토그램에서 가장 큰 직사각형

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

N의 범위가 100,000 이하 이므로 최소한 O(NlogN) 의 시간복잡도를 가져야 한다.

정렬 ? 하면 문제 자체의 의미가 없으므로 패스
높이를 기준으로 풀면 O(NM) 이 이미 1초를 훨씬넘기므로 패스

단순히 문제 자체가 요구하는 바는 넓이의 최댓값.. (질의)
그리고 O(NlogN) 의 시간복잡도...

세그먼트 트리를 이용해 구간질의를 해야겠네

일단 각 구간을 반으로 쪼개어 트리 노드형태로 만들어주자

이렇게 트리 노드를 초기화 하자 .
각 트리노드는 최솟값 인덱스 질의를 처리하기 편하게 각 구간의 최솟값(높이)를 가지는 인덱스를 표현하도록 하자.

void init(vector<int>& a,vector<int>& tree,int node,int start,int end)
{
	int mid = (start + end) / 2;
    if(start == end) // 리프노드 
    {
    	tree[node] = start;
    }
    else
    {
    	// 각 트리가 각각이 맡고 있는 구간의 최소 인덱스를 나타내도록
    	init(a, tree, node * 2, start, mid); 
        init(a, tree, node * 2 + 1, mid +1, end);
		if(a[tree[node * 2]] <= a[tree[node * 2 +1 ]])
        {
        	tree[node] = tree[node*2];
        }else
        {
        	tree[node] = tree[node*2+1];
        }
    }
}

처음 상태에서 최소 인덱스는 1이고, 높이는 1이다.
따라서, 넓이는 1 * 7 = 7
현재 구한 최소 인덱스에서 왼쪽과 오른쪽으로 나아갈 수 있으므로
왼쪽(0~0)과 오른쪽(2~6)으로 재귀를 진행한다.

현재 (0~0) 구간은 시작점과 끝점이 같으므로 여기서 재귀를 할 수 없으므로
그냥 현재의 넓이를 리턴한다.
(2~6) 구간에서 최솟값 인덱스는 4이고, 높이는 1이다.
따라서 넓이는 1 * ( 6 - 2 + 1) = 5
(2~6) 구간은 다시 (2~3) 과 (5~6) 구간으로 쪼갤 수 있다.

(2~3) 구간에서 최소 인덱스는 2이고 높이는 4이다.
넓이는 4 (3 - 2 +1 ) = 8
(5~6) 구간에서 최소 인덱스는 5이고 높이는 3이다.
넓이는 3 (6 - 5 + 1 ) = 6

마지막으로는 각각에서 남은거 한개씩 넓이를 구하면 함수는 끝이 난다.

큰 맥락으로 봤을때
① 최소 인덱스를 구한다 (구간 질의를 처리)
② 넓이를 산출한다. (넓이 구하는 함수)
최소 인덱스에서 왼쪽과 오른쪽으로 더 나아갈 수 있다면
분할해서 넓이를 계속 산출해 나간다 .

구간 질의

int query(vector<int>& a,vector<int>& tree,int node,int start,int end, int left, int right)
{
	if( left > end || right < start )
    {
    	return -1;
    }
    if( left <= start && end <= right)
    {
    	return tree[node];
    }
    int m1 = query(a,tree,node*2,start,mid,left,right);
    int m2 = query(a,tree,node*2+1,mid+1,end,left,right);
    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;
}