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

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

#include < stdio.h >

#include < math.h >

#include < vector >

#include < algorithm >

using namespace std ;

typedef long long ll;

int n;

int num[ 100001 ];

vector < int > segTree;

void makeSegTree( int node, int start, int end ) {

if (start = = end ) {

segTree[node] = start;

return ;

}

int mid = (start + end ) / 2 ;

makeSegTree(node * 2 , start, mid);

makeSegTree(node * 2 + 1 , mid + 1 , end );

if (num[segTree[node * 2 ]] < = num[segTree[node * 2 + 1 ]]) {

segTree[node] = segTree[node * 2 ];

}

else {

segTree[node] = segTree[node * 2 + 1 ];

}

}

int findIdx( int node, int start, int end , int left, int right) {

if (left > end | | right < start) return - 1 ;

if (left < = start & & end < = right) return segTree[node];

int mid = (start + end ) / 2 ;

int leftRes = findIdx(node * 2 , start, mid, left, right);

int rightRes = findIdx(node * 2 + 1 , mid + 1 , end , left, right);

if (leftRes = = - 1 )

return rightRes;

if (rightRes = = - 1 )

return leftRes;

if (num[leftRes] < = num[rightRes])

return leftRes;

else

return rightRes;

}

ll solve( int start, int end ) {

int numSize = n;

int m = findIdx( 1 , 0 , numSize - 1 , start, end );

ll area = (ll)( end - start + 1 ) * (ll)num[m];

if (start < = m - 1 ) {

ll tmp = solve(start, m - 1 );

area = max(tmp, area);

}

if (m + 1 < = end ) {

ll tmp = solve(m + 1 , end );

area = max(tmp, area);

}

return area;

}

int main( void ) {

while ( 1 ) {

scanf ( "%d" , & n);

if (n = = 0 ) break ;

for ( int i = 0 ; i < n; i + + )

scanf ( "%d" , & num[i]);

int treeHeight = ( int )ceil(log2(n));

int treeSize = ( 1 < < (treeHeight + 1 ));

segTree.resize(treeSize);

makeSegTree( 1 , 0 , n - 1 );

printf ( "%lld

" , solve( 0 , n - 1 ));

segTree.clear();

}

return 0 ;

}

from http://dizlet.tistory.com/22 by ccl(A) rewrite - 2021-08-30 22:00:18