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

안녕하세요. 오늘은 어려운 연속합 문제를 풀어볼 거에요.

문제

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

아이디어

각각의 문제에 대해서는 이분탐색을 통한 결정문제로 해결할 수 있습니다.
높이의 최솟값이 x일때 가능한가?
이는 높이가 x이상인 직사각형들만 남겨놓고 구간 [l,r]에서 1만 있는 연속합의 최댓값을 가져오면 할 수 있습니다.

하지만 문제는 이러한 쿼리들이 너무 많다는 것입니다.
이때는 병렬 이분탐색을 쓰면 됩니다.

일단 값들이 크기 때문에 값 압축을 합시다.
nums[i]는 i번째 작은 수이고 인덱스는 0부터 시작, 중복은 제거되어있습니다.
num_arr[x]는 값이 x인 수들의 인덱스들을 모두 모아놓은 벡터입니다.
qry에는 모든 쿼리의 값들이 들어가 있습니다. 인덱스는 1부터 시작입니다.
그다음 PBS를 해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

struct Tree {
    ll left, right, ans, all;
};

Tree tree[404040] = { {0,0,0,0} };
void init(ll s, ll e, ll node)
{
    tree[node] = { 0,0,0,0 };
    if (s == e) return;
    ll mid = (s + e) / 2;
    init(s, mid, node * 2);
    init(mid + 1, e, node * 2 + 1);
    return;
}
Tree Union(Tree A, ll s1, ll e1, Tree B, ll s2, ll e2)
{
    Tree res;
    res.all = A.all + B.all;
    res.left = A.left;
    res.right = B.right;
    res.ans = max({ A.ans,B.ans ,A.right + B.left });
    if (A.all == e1 - s1 + 1) res.left = max(res.left, A.all + B.left);
    if (B.all == e2 - s2 + 1) res.right = max(res.right, B.all + A.right);
    return res;
}
Tree Query(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return { 0,0,0,0 };
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    Tree first = Query(s, mid, node * 2, l, r), second = Query(mid + 1, e, node * 2 + 1, l, r);
    return Union(first, s, mid, second, mid + 1, e);
}
void change(ll s, ll e, ll node, ll idx)
{
    if (e < idx || idx < s) return;
    if (s == e)
    {
        tree[node] = { 1,1,1,1 };
        return;
    }

    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx);
    change(mid + 1, e, node * 2 + 1, idx);
    tree[node] = Union(tree[node * 2], s, mid, tree[node * 2 + 1], mid + 1, e);
}

ll Left[101010] = { 0 }, Right[101010] = { 0 }, Ans[101010] = { 0 };
vector <ll> mid[101010];
void mid_init()
{
    for (ll i = 0; i <= 100000; i++) mid[i].clear();
}

vector <ll> nums, num_arr[101010];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x, a, b, c, Q;
    vector <pair <ll, ll> > arr;
    vector <pair <pair <ll, ll>, ll> > qry;

    cin >> N;
    arr.push_back({ 0,0 }); //인덱스는 1부터
    for (i = 1; i <= N; i++)
    {
        cin >> a;
        arr.push_back({ a,i });
        nums.push_back(a);
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    ll numN = nums.size();
    for (i = 1; i <= N; i++)
        num_arr[lower_bound(nums.begin(), nums.end(), arr[i].first) - nums.begin()].push_back(i);
    sort(nums.begin(), nums.end(), greater<>());


    cin >> Q;
    qry.push_back({ {0,0},0 }); //인덱스는 1부터
    for (i = 1; i <= Q; i++)
    {
        cin >> a >> b >> c;
        qry.push_back({ {a,b},c });
        Left[i] = 0;
        Right[i] = numN - 1;
    }

    while (true) //PBS
    {
        mid_init();
        bool done = true;
        for (i = 1; i <= Q; i++)
        {
            if (Left[i] < Right[i])
            {
                done = false;
                mid[(Left[i] + Right[i]) / 2].push_back(i);
            }
        }
        if (done) break;

        init(1, N, 1);
        for (i = 0; i < numN; i++) //i번째 큰 직사각형까지 있음
        {
            for (ll j : num_arr[numN - i - 1]) change(1, N, 1, j);
            for (ll idx : mid[i])
            {
                if (Query(1, N, 1, qry[idx].first.first, qry[idx].first.second).ans >= qry[idx].second)
                {
                    Ans[idx] = nums[i];
                    Right[idx] = i;
                }
                else Left[idx] = i + 1;
            }
        }
    }

    for (i = 1; i <= Q; i++)
    {
        if (Ans[i]) cout << Ans[i] << "\n";
        else cout << nums[Left[i]] << "\n";
    }
}

감사합니다.