[BOJ 1725] 히스토그램

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

Tag : DSU

 

풀이

히스토그램은 모노톤 큐, 분할정복, 세그먼트 트리 풀이가 있다는 것이 잘 알려진 문제입니다.

이 히스토그램을 유니온 파인드로도 풀 수 있는데 저는 이 풀이가 가장 쉽고 구현도 편한다고 생각합니다.

 

일단 (a[i], i)를 관리하는 벡터 v를 만들고 이를 내림차순으로 정렬합니다. 

그리고 이를 순회하며 a[i - 1], a[i + 1]을 보며 a[i] 이상인 경우 merge해줍니다.

그러면 i와 merge된 원소들은 항상 a[i] 이상의 값을 가지고 있으며 인접한 원소들을 통해 묶이게됩니다.

이 상태에서 sz[find(i)]와 a[i]를 통해 a[i]가 히스토그램에서 가장 낮은 원소일 경우의 최대를 구할 수 있고

이를 모든 원소에 반복해보면 답을 구할 수 있습니다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n;
int a[101010];
int pa[101010];
int sz[101010];

int find(int a) {
    if(a == pa[a]) return a;
    else return pa[a] = find(pa[a]);
}

void merge(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    pa[b] = a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
    
    cin >> n;
    vector<pair<int, int>> v(n);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        v[i - 1] = {a[i], i};
        pa[i] = i;
        sz[i] = 1;
    }
    sort(v.begin(), v.end(), greater<>());
    ll ans = 0;
    for(auto &[x, idx] : v) {
        if(idx >= 2 and a[idx - 1] >= x) merge(idx, idx - 1);
        if(idx < n and a[idx + 1] >= x) merge(idx, idx + 1);
        ans = max(ans, 1ll * x * sz[find(idx)]);
    }
    cout << ans << endl;
}