BOJ 30854 Farm

문제 링크입니다.

문제 요약

히스토그램 위에 $N$개의 점이 있습니다. 히스토그램 안에 직사각형을 몇 개 그려 모든 점이 적어도 하나의 직사각형의 경계 또는 내부에 포함되게끔 해야 합니다. 그려야 하는 직사각형 개수의 최솟값을 구하세요.

넣기 힘든 것부터

직사각형의 높이가 결정되어 있다면, 너비는 될 수 있는 한 꽉 채워서 그리는 게 이득입니다.

맨 위에 있는 점을 생각해봅시다. 이 점보다 높이 직사각형을 그릴 필요는 없습니다. 그래봤자 직사각형에 추가되는 점이 없으니… 따라서 이 점을 포함하도록 직사각형을 그리면, 이 점이 천장이 되고, 양옆으로 될 수 있는 한 넓힌 상태에서 아래로 쭉 내린 모양이 됩니다.

이 논의는 각 점이 직사각형에 포함되지 않은 점 중 맨 위가 되는 모든 경우에 적용됩니다. 따라서 점을 높이가 높은 순으로 확인하면, 직사각형을 그리는 것은 어떤 구간을 추가하는 것으로 나타나고, 직사각형에 포함되어 있는지 확인하는 것은 해당 점을 포함하는 구간이 존재하는 지 확인하는 것으로 충분해집니다.

구간을 추가하고 확인하는 것은 세그먼트 트리나 펜윅 트리로 가능하고, 각 점 별로 직사각형을 그릴 때 양 옆으로 얼마나 넓혀야 하는지는 각 x좌표마다의 높이를 전처리한 최솟값 세그먼트 트리에서 이분 탐색으로 찾을 수 있습니다. 따라서 총 시간 복잡도는 ${\cal O}((N+M) \lg (N+M))$입니다.

코드

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

int ub[1010101], wall[4040404], vis[1010101], m, n, lx;

void vis_upd(int l, int r){
	r++; for(;r <= lx; r += r&-r) vis[r]--;
	for(;l <= lx; l += l&-l) vis[l]++;
}

int vis_qry(int i){
	int ret = 0;
	for(;i;i-=i&-i) ret += vis[i];
	return ret;
}

void init(int now, int l, int r){
	if(l == r){
		wall[now] = ub[l]; return;
	}
	init(now<<1, l, mid); init(now<<1|1, mid+1, r);
	wall[now] = min(wall[now<<1], wall[now<<1|1]);
}

int l_qry(int now, int l, int r, int R, int y){
	if(R < l) return 0;
	if(wall[now] >= y) return 0;
	if(l == r) return r+1;
	int rr = l_qry(now<<1|1, mid+1, r, R, y);
	if(rr) return rr;
	return l_qry(now<<1, l, mid, R, y);
}

int r_qry(int now, int l, int r, int L, int y){
	if(L > r) return 0;
	if(wall[now] >= y) return 0;
	if(l == r) return l-1;
	int ll = r_qry(now<<1, l, mid, L, y);
	if(ll) return ll;
	return r_qry(now<<1|1, mid+1, r, L, y);
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> m >> n >> lx; lx++; ub[0] = -1;
	for(int i = 1; i < m/2; i++){
		int by, bx; cin >> by >> bx; bx++;
		for(int i = lx; i <= bx; i++) ub[i] = max(ub[i], by);
		lx = bx;
	}
	int ly; cin >> ly; lx++; ub[lx] = -1; init(1, 0, lx);
	vector<pii> p;
	for(int i = 1; i <= n; i++){
		int px, py; cin >> px >> py; px++;
		p.push_back({py, px});
	}
	sort(p.begin(), p.end(), greater<pii>());
	int ans = 0;
	for(auto& [y, x] : p){
		if(vis_qry(x)) continue;
		ans++;
		int L = l_qry(1, 0, lx, x-1, y);
		int R = r_qry(1, 0, lx, x+1, y);
		vis_upd(L, R);
	}
	cout << ans;
}