백준 16977번 히스토그램에서 가장 큰 직사각형과 쿼리

문제 요약

길이 N인 히스토그램이 주어진다. 다음과 같은 쿼리를 처리해야 한다.

l r w 가 주어지면 [l,r]에 있는 히스토그램만 있을 때, 너비가 w인 직사각형들 중에서 가장 높은 직사각형의 높이를 출력해야 한다.

 

N, Q 둘다 최대 10만이다.

풀이

어떤 배열이 0 혹은 1로 이루어져 있는데 어떤 구간에서 연속으로 1인 구간의 최대 길이를 계산하는 세그먼트 트리를 생각해보자.

금광세그로 유명한 그것을 살짝 변형해보면 될 거 같다.

 

각 노드에서 관리할 정보는 담당 구간의 제일 왼쪽에 시작하는 1의 연속 구간의 길이와 제일 오른쪽부터 시작하는 1의 연속구간의 길이이다. 그리고 제일 긴 1의 연속구간의 길이이다.

그러면 두 구간을 합해줄 때 새로운 노드의 왼쪽 1의 길이는 왼쪽을 담당하는 노드의 왼쪽 길이거나 만약 그 길이가 왼쪽 노드가 담당하는 구간의 길이가 동일하다면 구간 길이에다가 오른쪽 구간의 왼쪽 길이도 추가한다.

각각을 left, right, mx라고 하자. 아래와 같은 의사코드로 구간을 합쳐주는 게 가능하다.

new_left = leftnode.left
if new_left == leftnode.len:
    new_left += rightnode.left
new_right = rightnode.right
if new_right == rightnode.len:
    new_right += leftnode.right
new_len = leftnode.len + rightnode.len
nex_mx = max(leftnode.mx, rightnode.mx, new_left, new_right)

이제 히스토그램에 높이들을 내림차순 정렬하자. 정렬한 배열을 $h'$라고 하겠다.

그리고 $segtree_i$는 $h'_i$이상인 $h_k$에 대해서 $k$ 위치에 1이 켜져있는 세그트리라고 하자.

그러면 쿼리가 들어왔을 때, $[l,r]$ 쿼리의 값이 $w$이 상인 $segtree_i$들 중에서 $i$가 가장 작은 $segtree_i$를 찾아주면 된다. 그 때의 $h'_i$가 답이 된다.

 

이제 모든 $segtree_i$를 위에서 설명한 대로 PST로 구성해주고 이분탐색을 진행하면 쿼리에 대답할 수 있다. 쿼리당 시간복잡도는 $O(log^2N)$이 된다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 1e5;
int N, Q;
vector<ll> v;
vector<pair<ll,int>> h;

struct Node {
    int lsum=0, rsum=0, mx=0;
    int l=0, r=0, sz=0;
};

int node_cnt;
vector<Node> tree(40*MXN);
vector<int> roots(MXN+5);

void init(int node, int s, int e) {
    if(s == e) tree[node].sz = 1;
    else {
        int mid = s + e >> 1;
        int n1 = node << 1, n2 = node << 1 | 1;
        tree[node].l = n1; tree[node].r = n2;
        init(n1, s, mid);
        init(n2, mid+1, e);
        tree[node].sz = tree[n1].sz + tree[n2].sz;
    }
}

void combine(Node &a, Node &b, Node &ret) {
    if(a.mx == -1) {
        ret = b; return ;
    }
    else if(b.mx == -1) {
        ret = a; return ;
    }
    ret.sz = a.sz + b.sz;
    ret.lsum = a.lsum;
    if(a.lsum && a.lsum == a.sz) ret.lsum += b.lsum;
    ret.rsum = b.rsum;
    if(b.rsum && b.rsum == b.sz) ret.rsum += a.rsum;
    ret.mx = max(a.mx, b.mx);
    ret.mx = max(ret.mx, max(ret.lsum, ret.rsum));
    ret.mx = max(ret.mx, a.rsum + b.lsum);
}

void update(int node, int s, int e, int idx) {
    if(s == e) {
        tree[node].lsum = tree[node].rsum = tree[node].mx = 1;
        //assert(tree[node].l == 0);
        //assert(tree[node].r == 0);
    }
    else {
        int mid = s + e >> 1;
        int n1 = tree[node].l, n2 = tree[node].r;
        if(idx <= mid) {
            tree[node].l = node_cnt;
            tree[node_cnt++] = tree[n1];
            //assert(tree[tree[node].l].sz + tree[tree[node].r].sz == tree[node].sz);
            update(tree[node].l, s, mid, idx);
        }
        else {
            tree[node].r = node_cnt;
            tree[node_cnt++] = tree[n2];
            //assert(tree[tree[node].l].sz + tree[tree[node].r].sz == tree[node].sz);
            update(tree[node].r, mid+1, e, idx);
        }
        //assert(tree[tree[node].l].sz + tree[tree[node].r].sz == tree[node].sz);
        combine(tree[tree[node].l], tree[tree[node].r], tree[node]);
    }
}

Node query(int node, int s, int e, int l, int r) {
    if(r < s || l > e) {
        Node ret = Node();
        ret.mx = -1;
        return ret;
    }
    if(l <= s && e <= r) return tree[node];
    int mid = s + e >> 1;
    int n1 = tree[node].l, n2 = tree[node].r;
    Node node1 = query(n1, s, mid, l, r);
    Node node2 = query(n2, mid+1, e, l, r);
    Node ret = Node();
    combine(node1, node2, ret);
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=1;i<=N;++i) {
        ll x; cin >> x;
        h.emplace_back(x,i); v.push_back(x);
    }
    sort(h.begin(), h.end(), greater<>());
    v.push_back(0);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=0;i<h.size();++i) h[i].first = lower_bound(v.begin(), v.end(), h[i].first) - v.begin();
    node_cnt = 1;
    while(node_cnt < N) node_cnt <<= 1; node_cnt <<= 1;
    int tsz = node_cnt;
    init(1, 1, N);
    roots[0] = 1;
    int idx = h[0].first;
    roots[idx] = roots[0];
    assert(idx == v.size() - 1);
    for(int i=0;i<h.size();++i) {
        if(h[i].first != idx) {
            --idx;
            roots[idx] = roots[idx+1];
        }
        tree[node_cnt] = tree[roots[idx]];
        roots[idx] = node_cnt++;
        update(roots[idx], 1, N, h[i].second);
    }
    assert(idx == 1);
    cin >> Q;
    for(int i=0;i<Q;++i) {
        int l, r, w;
        cin >> l >> r >> w;
        int lo = 1, hi = v.size() - 1;
        int ans = 0;
        while(lo <= hi) {
            int mid = lo + hi >> 1;
            int thr = query(roots[mid], 1, N, l, r).mx;
            if(thr >= w) {
                ans = mid;
                lo = mid + 1;
            }
            else hi = mid-1;
        }
        assert(ans > 0);
        cout << v[ans] << '\n';
    }
    return 0;
}