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

• 입력: 직사각형의 수 n(1≤n≤100,000) , n개의 직사각형의 높이 hi(1≤hi≤1,000,000,000), n = 0이면 종료
• 출력: 각 테스트케이스에 대해서, 히스토그램에서 가장 큰 직사각형의 넓이
• 알고리즘: 세그먼트 트리
• 실패한 소스코드
?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cmath> #include <vector> using namespace std;   #define ll long long   #define MAX 1000*1000*1000 + 1   ll min(ll a, ll b) { return (a < b ? a : b); } ll max(ll a, ll b) { return (a > b ? a : b); }   ll init(vector<ll>& height, vector<ll>& arr, ll node, ll start, ll end) {     if (start == end) return height[node] = arr[start];     else return height[node] = min(init(height, arr, node * 2, start, (start + end) / 2), init(height, arr, node * 2 + 1, (start + end) / 2 + 1, end)); }   ll retHeight(vector<ll>& tree, vector<ll>& height, ll node, ll start, ll end) {     if (start == end) return tree[node] = height[node];     if (height[node] == MAX) return 0;     tree[node] = (end - start + 1) * height[node];     ll max_height = tree[node];     max_height = max(max_height, retHeight(tree, height, node * 2, start, (start + end) / 2));     max_height = max(max_height, retHeight(tree, height, node * 2 + 1, (start + end) / 2 + 1, end));     return max_height; }   int main() {     int n;     scanf("%d", &n);     while (n != 0) {         vector<ll> arr(n);         for (int i = 0; i < n; i++)             scanf("%lld", &arr[i]);           ll h = (ll)ceil(log2(n));         ll tree_size = (1 << (h + 1));           vector<ll> height(tree_size, MAX);         vector<ll> tree(tree_size);         init(height, arr, 1, 0, n - 1);         printf("%lld\n", retHeight(tree, height, 1, 0, n - 1));             scanf("%d", &n);     }       return 0; }

세그먼트 트리를 이용했는데, 트리에 각 구간에 대해 가장 낮은 높이를 저장해두고 높이를 따로 저장한다.

실패한 이유로는 위와 같이 하게 되면 각 구간, 1/2만큼의 사이즈에 대해서만 높이를 구하기 때문에 예를 들면 n=8일때 h3~h7까지의 넓이가 가장 크다고 해도 구할 수 없다.

즉, 가장 작은 높이를 가진 인덱스를 트리에 저장해두고 계산하는 방식으로 해야한다고 생각했다. 

• 성공한 소스코드
?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cmath> #include <vector> using namespace std;   #define ll long long   #define MAX 1000*1000*1000 + 1   ll max(ll a, ll b) { return (a > b ? a : b); }   void init(vector<ll>& height, vector<ll>& arr, int node, int start, int end) {     if (start == end) height[node] = start;     else {         init(height, arr, node * 2, start, (start + end) / 2);         init(height, arr, node * 2 + 1, (start + end) / 2 + 1, end);         height[node] = (arr[height[node * 2]] <= arr[height[node * 2 + 1]] ? height[node * 2] : height[node * 2 + 1]);     } }   int retHeight(vector<ll>& height, vector<ll>& arr, int node, int left, int right, int start, int end) {     if (end < left || right < start ) return -1;     if (left <= start && end <= right) return height[node]; // 구간 내에 있으면     int l = retHeight(height, arr, node * 2, left, right, start, (start + end) / 2), r = retHeight(height, arr, node * 2 + 1, left, right, (start + end) / 2 + 1, end);     if (l == -1) return r;     if (r == -1) return l;     return (arr[l] <= arr[r] ? l : r); }   ll maxS(vector<ll>& height, vector<ll>& arr, int left, int right, int n) {     int index = retHeight(height, arr, 1, left, right, 0, n - 1);     ll max_s = (ll)(right - left + 1)*arr[index];     if (left <= index - 1)         max_s = max(max_s, maxS(height, arr, left, index - 1, n));     if (right >= index + 1)         max_s = max(max_s, maxS(height, arr, index + 1, right, n));       return max_s; }   int main() {     int n;     scanf("%d", &n);     while (n != 0) {         vector<ll> arr(n);         for (int i = 0; i < n; i++)             scanf("%lld", &arr[i]);           ll h = (ll)ceil(log2(n));         ll tree_size = (1 << (h + 1));           vector<ll> height(tree_size, MAX);         init(height, arr, 1, 0, n - 1);         printf("%lld\n", maxS(height, arr, 0, n-1, n));             scanf("%d", &n);     }       return 0; }

인터넷을 참고하여 문제를 풀었는데 위 식은 트리에 가장 낮은 높이의 인덱스를 저장해두고, 그 중 가장 큰 넓이를 찾는 방식이다. 소스코드를 참고한 사이트는 아래 첨부해놓았다. 아직은 미숙한거 같아, 유사한 문제를 알고스팟에 풀고 다른 문제를 다시 도전해볼 예정이다.
세그먼트 트리에서는 어떤 기준으로 저장하냐와 접근하냐가 중요한 키워드인 것 같다.

• 참고: https://www.acmicpc.net/problem/6549
• 소스코드 참고: http://jason9319.tistory.com/44