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

문제 링크입니다.

문제 요약

히스토그램의 $[l,r]$ 구간 안에 넣을 수 있는 너비 $w$짜리 직사각형의 최대 높이를 $Q$번 구하세요.

결정 문제 풀기

$[l, r]$ 안에 $w \times h$ 크기의 직사각형을 집어넣을 수 있는 지 판정하는 문제를 해결해 봅시다.

히스토그램에 직사각형을 넣는 문제를 푸는 방법 중 하나로 Union-Find를 이용해 높이가 높은 직사각형부터 합치면서 연결 요소의 너비를 구하는 방법이 있습니다. 이를 응용하면 높이가 $h$ 이상인 직사각형만 남긴 채로 연결 요소를 구성한 뒤, 구간 $[l, r]$에 포함되는 최대 연결 요소 크기를 구하는 방식으로 위의 결정 문제를 해결할 수 있습니다.

최대 연속 합을 구하는 세그먼트 트리를 이용하면 $h$가 큰 순서대로 직사각형을 추가 후 구간 최대 연속 합을 구하는 방식으로 ${\cal O}(N \lg N)$에 한 쿼리를 해결할 수 있습니다. 총 시간 복잡도는 ${\cal O}(NQ \lg N)$이라 시간 초과를 피하기 어렵습니다.

최적화 문제 풀기

직사각형이 추가되는 모든 경우마다 구간 최대 판정을 할 필요가 없습니다. $h$에 대한 이분 탐색을 적용하면 쿼리마다 ${\cal O}(\lg N)$번의 최댓값 쿼리로 답을 얻어낼 수 있습니다.

이 과정에서 ${\cal O}(\lg N)$번의 세그먼트 트리 재구성이 필요합니다. 각 쿼리마다 세그먼트 트리를 따로 초기화해서 쓸 필요는 없으니 세그먼트 트리를 한 번 구성할 때마다 모든 쿼리에 대한 이분 탐색을 동시에 처리해 줄 수 있습니다. 총 ${\cal O}(Q \lg N)$번의 쿼리와 ${\cal O}(N \lg N)$번의 업데이트가 필요하므로, 시간 복잡도 ${\cal O}((N+Q) \lg^2 N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

struct Node{
	int tot, lcnt, rcnt, ans;
} tree[404040];

struct Qry{
	int l, r, w;
}; vector<Qry> q;
vector<int> bucket[101010];
vector<int> rollback;

int L[101010], R[101010];
vector<pii> h;

Node merge(Node l, Node r){
	Node ret;
	ret.tot = l.tot+r.tot;
	ret.lcnt = l.lcnt+(l.lcnt == l.tot)*r.lcnt;
	ret.rcnt = r.rcnt+(r.rcnt == r.tot)*l.rcnt;
	ret.ans = max({l.ans, r.ans, l.rcnt+r.lcnt});
	return ret;
}

void init(int now, int l, int r){
	tree[now] = {r-l+1,0,0,0}; if(l == r) return;
	init(now<<1, l, mid); init(now<<1|1, mid+1, r);
}

void upd(int now, int l, int r, int i){
	if(l == r){
		tree[now] = {1,1,1,1};
		return;
	}
	if(i <= mid) upd(now<<1, l, mid, i);
	else upd(now<<1|1, mid+1, r, i);
	tree[now] = merge(tree[now<<1], tree[now<<1|1]);
}

Node qry(int now, int l, int r, int L, int R){
	if(l > R || L > r) return {0,0,0,0};
	if(L <= l && r <= R) return tree[now];
	return merge(qry(now<<1, l, mid, L, R), qry(now<<1|1, mid+1, r, L, R));
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 1; i <= n; i++){
		int t; cin >> t; h.push_back({t, i});
	} h.push_back({1234567890, 0});
	sort(h.begin(), h.end(), greater<>());

	int Q; cin >> Q; q.push_back({0,0,0});
	for(int i = 1; i <= Q; i++){
		int l, r, w; cin >> l >> r >> w;
		q.push_back({l, r, w});
		L[i] = 0; R[i] = n;
	}
	while(1){
		init(1, 1, n);
		bool done = 1;
		for(int i = 1; i <= Q; i++){
			if(L[i] >= R[i]) continue;
			done = 0;
			bucket[L[i]+R[i]>>1].push_back(i);
			rollback.push_back(L[i]+R[i]>>1);
		}
		if(done) break;
		for(auto& j : bucket[0]) L[j] = 1;
		for(int i = 1; i <= n; i++){
			upd(1, 1, n, h[i].second);
			for(auto& j : bucket[i]){
				if(qry(1, 1, n, q[j].l, q[j].r).ans >= q[j].w) R[j] = i;
				else L[j] = i+1;
			}
		}
		for(auto& i : rollback) bucket[i].clear();
		rollback.clear();
	}
	for(int i = 1; i <= Q; i++) cout << h[L[i]].first << '\n';
	
}