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

문제

링크: https://www.acmicpc.net/problem/16977
요약: 히스토그램의 높이 배열 h[1..N]에서 쿼리 (l, r, w)가 주어지면, 구간 [l, r] 내부의 길이 w인 연속 구간들 중 최솟값이 최대가 되는 값을 출력합니다. (너비가 고정이므로 넓이 최대 ≡ 높이 최대)

입력/출력

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
입력
7
2 1 4 5 1 3 3
8
3 4 2
4 7 2
2 5 1
2 5 2
2 5 3
2 5 4
1 3 2
6 7 2

출력
4
3
5
4
1
1
1
3

접근 개요

너비가 w로 고정되면, 최대 넓이는 곧 길이 w 윈도우의 최솟값을 최대화하는 문제입니다.
임계값 T를 고정했을 때, h[i] ≥ T인 위치를 1로 표시하면, 구간 [l, r] 안에 길이 w 이상의 연속 1 구간이 존재하는지의 여부가 단조입니다(T가 커질수록 성립이 어렵다).
이 단조성을 이용해 높이값에 대해 병렬 이분탐색(Parallel Binary Search, PBS)을 돌리고, 각 임계값 검증은 “연속 1의 최댓값”을 유지하는 세그먼트 트리로 처리합니다.

flowchart TD
  A[높이 좌표압축] --> B[쿼리별 T에 대한 PBS]
  B --> C{임계값 T에 대해
           h[i]≥T → 1,
           아니면 0}
  C --> D[세그트리로 [l,r]의 연속 1 최댓값 질의]
  D --> E{best ≥ w?}
  E -- 예 --> F[lo = mid]
  E -- 아니오 --> G[hi = mid - 1]
  F --> H[모든 쿼리 수렴]
  G --> H

알고리즘 설계

좌표압축: 높이들을 정렬·중복제거하여 인덱스화(랭크).
PBS: 각 쿼리에 대해 높이 랭크 구간에서 이분탐색. 같은 mid(임계 랭크)를 요구하는 쿼리들을 버킷으로 묶어 한 번에 검증.
활성화 전략: 랭크가 큰 순서로 인덱스를 활성화(1로 갱신). 같은 라운드에서 임계값을 내림차순으로 처리하며, 포인터 1회 전진으로 누적 활성화 → 매 라운드 O((활성화 건수) log N + (검증 쿼리 수) log N).
세그트리 노드 정보: len, pref, suff, best(전체 길이, 앞/뒤 연속 1 길이, 구간 내 연속 1 최댓값). 병합 시 best = max(left.best, right.best, left.suff + right.pref).
정당성: (1) T에 대한 “존재 여부”는 단조이므로 이분탐색 가능. (2) 길이 w 윈도우의 최솟값 ≥ T ⇔ 표시배열에서 연속 1 구간 길이 ≥ w가 존재.

복잡도

라운드 수는 O(log M) (M=서로 다른 높이 개수). 라운드마다 활성화/질의는 세그트리로 O(log N).
전체: O((N + Q) log M log N). N, Q ≤ 1e5에서 충분히 통과합니다.

구현 (C++)

  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
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int l, r, w;
};

struct Node {
    int len, pref, suff, best;
    Node(int l=0, int p=0, int s=0, int b=0): len(l), pref(p), suff(s), best(b) {}
};

struct SegTree {
    int n;
    vector<Node> st;
    SegTree(int n=0): n(n), st(4*n+4) {}

    static Node mergeNode(const Node &a, const Node &b) {
        if (a.len == 0) return b;
        if (b.len == 0) return a;
        Node res;
        res.len = a.len + b.len;
        res.pref = (a.pref == a.len) ? (a.len + b.pref) : a.pref;
        res.suff = (b.suff == b.len) ? (b.len + a.suff) : b.suff;
        res.best = max({a.best, b.best, a.suff + b.pref});
        return res;
    }

    void build(int p, int l, int r) {
        if (l == r) {
            st[p] = Node(1, 0, 0, 0);
            return;
        }
        int m = (l + r) >> 1;
        build(p<<1, l, m);
        build(p<<1|1, m+1, r);
        st[p] = mergeNode(st[p<<1], st[p<<1|1]);
    }

    void update(int p, int l, int r, int idx) {
        if (l == r) {
            st[p] = Node(1, 1, 1, 1);
            return;
        }
        int m = (l + r) >> 1;
        if (idx <= m) update(p<<1, l, m, idx);
        else update(p<<1|1, m+1, r, idx);
        st[p] = mergeNode(st[p<<1], st[p<<1|1]);
    }

    Node query(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return Node(0,0,0,0);
        if (ql <= l && r <= qr) return st[p];
        int m = (l + r) >> 1;
        Node left = query(p<<1, l, m, ql, qr);
        Node right = query(p<<1|1, m+1, r, ql, qr);
        return mergeNode(left, right);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<int> h(N+1);
    for (int i = 1; i <= N; ++i) cin >> h[i];

    int Q; cin >> Q;
    vector<Query> qs(Q);
    for (int i = 0; i < Q; ++i) {
        int l, r, w; cin >> l >> r >> w;
        qs[i] = {l, r, w};
    }

    // 좌표압축
    vector<int> vals;
    vals.reserve(N);
    for (int i = 1; i <= N; ++i) vals.push_back(h[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int M = (int)vals.size();

    vector<int> rankH(N+1);
    for (int i = 1; i <= N; ++i) {
        rankH[i] = int(lower_bound(vals.begin(), vals.end(), h[i]) - vals.begin());
    }

    // 인덱스를 높이 랭크 내림차순으로 정렬
    vector<int> order(N);
    iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return rankH[a] > rankH[b];
    });

    // 병렬 이분탐색 (랭크 공간)
    vector<int> lo(Q, 0), hi(Q, M-1), mid(Q, 0);
    vector<vector<int>> bucket(M);
    vector<char> used(M, 0);
    vector<int> usedList;
    usedList.reserve(M);

    SegTree st(N);

    auto check_and_update = [&](int t) {
        for (int qi : bucket[t]) {
            const auto &qq = qs[qi];
            Node res = st.query(1, 1, N, qq.l, qq.r);
            if (res.best >= qq.w) lo[qi] = mid[qi];
            else hi[qi] = mid[qi] - 1;
        }
    };

    while (true) {
        bool any = false;
        for (int i = 0; i < Q; ++i) {
            if (lo[i] < hi[i]) {
                any = true;
                mid[i] = (lo[i] + hi[i] + 1) >> 1;
                bucket[mid[i]].push_back(i);
                if (!used[mid[i]]) {
                    used[mid[i]] = 1;
                    usedList.push_back(mid[i]);
                }
            }
        }
        if (!any) break;

        sort(usedList.begin(), usedList.end());
        // 같은 라운드: 임계 랭크 내림차순으로 처리하면서 인덱스 활성화 누적
        st.build(1, 1, N);
        int p = 0;
        for (int k = (int)usedList.size()-1; k >= 0; --k) {
            int t = usedList[k];
            while (p < N && rankH[order[p]] >= t) {
                st.update(1, 1, N, order[p]);
                ++p;
            }
            check_and_update(t);
        }

        for (int t : usedList) {
            bucket[t].clear();
            used[t] = 0;
        }
        usedList.clear();
    }

    for (int i = 0; i < Q; ++i) {
        cout << vals[lo[i]] << '\n';
    }
    return 0;
}