BOJ 15259 Buffalo Barricades

문제 링크입니다.

문제 요약

좌표평면의 1사분면 상의 $N$개의 위치에 버팔로가 있습니다. $M$개의 쿼리를 처리하는데, 각 쿼리는 어떤 점을 기준으로 다른 울타리나 좌표축에 닿을 때까지 왼쪽과 아래쪽으로 뻗는 울타리를 설치한 뒤, 해당 울타리로 분리되는 왼쪽 아래 영역의 버팔로 수를 묻습니다. 설치한 울타리는 누적됩니다.

풀이

새로운 울타리를 뻗으면 처음으로 닿는 벽에서 정지하기 때문에, 기존의 한 영역 안에서 새로운 울타리가 생겨 해당 영역을 분할하는 꼴이 됩니다. 따라서 모든 울타리를 설치한 뒤 생기는 영역의 수는 $M+1$개임을 알 수 있습니다. 울타리로 갇히지 않은 외부 영역을 제외한 각 영역을 그 맨 오른쪽 위 모서리 = 울타리의 기둥 = 쿼리 번호와 일대일로 매칭할 수 있음을 의미합니다.

집합을 분리하는 것보다 합치는 게 더 쉽기 때문에 쿼리를 역순으로 처리하는 방법을 고려합니다. 모든 울타리를 설치한 상태에서, 각 영역에 버팔로가 몇 마리씩 있는지 센 뒤에 마지막으로 설치된 울타리부터 제거하면서 영역을 합치는 방식으로 문제를 해결합시다.

최종 영역 구분하기

영역을 구분하는 근본적인 이유는 각 버팔로가 어느 영역에 속하는지 알기 위함입니다. 만약 $x$축을 기준으로 스위핑하면서 버팔로를 맞는 영역에 매칭하는 방식을 취한다면, 버팔로는 가장 가까운 천장에 해당하는 영역에 포함되므로 가로로 생성되는 울타리만 관리해 주어도 충분합니다.

자신보다 높은 세로 울타리에 의해서만 가로 울타리가 막힐 수 있다는 점으로부터, 울타리를 $y$좌표가 큰 것부터 추가하면서 쿼리 순서에 맞게 세로 울타리를 잘라내는 방법을 생각할 수 있습니다.

처음으로 닿는 왼쪽의 세로 울타리는 세로 울타리의 $x$좌표를 인덱스로 갖고 구간 내 울타리 중 쿼리 상 순서의 최솟값을 관리하는 세그먼트 트리 위에서 이분 탐색을 통해 ${\cal O}(\lg^2 M)$에 찾을 수 있습니다. 이를 바탕으로 가로 울타리가 차지하는 구간을 얻을 수 있고, 해당 구간 내의 다른 세로 울타리는 이번에 설치한 가로 울타리에 의해 잘리게 됩니다. 구간을 INF로 바꾸는 레이지 연산과 새로운 세로 울타리를 설치하는 연산을 섞어서 ${\cal O}(\lg M)$에 구현할 수 있습니다.

버팔로 배치하기

전술한 바와 같이 버팔로와 가로 울타리를 동시에 $x$좌표 기준으로 스위핑하면서 각 버팔로를 자신에게 가장 가까운 천장에 매칭할 것입니다. 울타리의 양 끝점을 이벤트로 넣고 정렬한 뒤 이벤트에 따라 셋에 천장을 추가하거나 제거하면서 이분 탐색으로 버팔로마다 가장 가까운 천장을 찾아 주면 총 ${\cal O}((N+M) \lg M)$에 구현할 수 있습니다.

합칠 영역 찾기

풀이의 개요에서 각 울타리가 배치될 때 하나의 영역을 둘로 분할한다고 언급했습니다. 이는 역으로 각 울타리를 쿼리 역순으로 제거하면 정확히 한 번의 영역 합성이 일어난다는 뜻이 되고, 이때 합쳐지는 영역은 제거한 울타리에 대응하는 영역과 그 바로 오른쪽에 위치하는 영역이 됩니다.

각 울타리가 제거될 때 어느 영역과 합쳐지게 되는 지를 영역을 구분하는 과정에서 함께 전처리합니다. 울타리를 추가하는 순서가 $y$좌표가 큰 순서기 때문에, 기존에 추가된 세로 울타리 중 이번에 설치할 울타리보다 오른쪽에 있는 울타리는 모두 다른 울타리에 막히지 않았다면 이번에 설치할 울타리를 포함할 수 있습니다.

따라서 그리디하게 가장 가까운 오른쪽 울타리와 매칭해 줄 수 있습니다. 만약 오른쪽의 울타리가 먼저 없어진다면 해당 울타리로 구분되었던 영역이 합쳐진 영역을 찾아가 합쳐주면 되는 것이라, Union-Find를 통해 쉽게 관리할 수 있게 됩니다.

존재하는 가장 가까운 오른쪽 세로 울타리는 마찬가지로 셋을 이용하면 각 울타리의 삽입/삭제 및 탐색이 ${\cal O}(M)$번 필요하므로 ${\cal O}(M \lg M)$에 이 과정을 모두 수행할 수 있습니다.

따라서 총 시간 복잡도 ${\cal O}((N+M) \lg M + M \lg^2 M)$에 문제를 해결할 수 있습니다.

코드

#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>;
const ll INF = 1e9+7;

map<int, int> xcoord, ycoord, rfence;

struct G{
	int x; int y; int idx;
} fence_event[303030];

struct Garo{
	int l; int r; int h; int idx;
};

pii buff[303030];

struct Event{
	int x; int idx; int h;
};

int tree[1818181], n, m;
bool lazy[1818181];

vector<Event> event;

void prop(int now, int l, int r){
	if(!lazy[now]) return;
	tree[now] = INF;
	if(l != r) lazy[now<<1] = lazy[now<<1|1] = 1;
	lazy[now] = 0; 
}

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

void boom(int now, int l, int r, int L, int R){
	prop(now, l, r);
	if(l > R || L > r) return;
	if(L <= l && r <= R){lazy[now] = 1; prop(now, l, r); return;}
	boom(now<<1, l, mid, L, R); boom(now<<1|1, mid+1, r, L, R);
	tree[now] = min(tree[now<<1], tree[now<<1|1]);
}

int qry(int now, int l, int r, int R){
	prop(now, l, r);
	if(l > R) return INF;
	if(r <= R) return tree[now];
	return min(qry(now<<1, l, mid, R), qry(now<<1|1, mid+1, r, R));
}

int Walk(int now, int l, int r, int R, int v){
	prop(now, l, r);
	if(l == r){
		if(tree[now] >= v) return 0;
		return l;
	}
	if(mid >= R) return Walk(now<<1, l, mid, R, v);
	prop(now<<1|1, mid+1, r);
	if(tree[now<<1|1] < v){
		int qr = Walk(now<<1|1, mid+1, r, R, v);
		if(qr) return qr;
	}
	return Walk(now<<1, l, mid, R, v);
}

int getMaxIdx(int R, int v){
	if(qry(1, 1, m+1, R) >= v) return 0;
	return Walk(1, 1, m+1, R, v);
}

int par[303030], nxt[303030];

int f(int x){
	return par[x] <= 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y); if(x == y) return;
	swap(x, y); par[x] += par[y]; par[y] = x;

}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n; for(int i = 1; i <= n; i++) cin >> buff[i].first >> buff[i].second;
	cin >> m; for(int i = 1; i <= m; i++){
		cin >> fence_event[i].x >> fence_event[i].y;
		fence_event[i].idx = i;
		xcoord[fence_event[i].x] = 1;
		ycoord[fence_event[i].y] = 1;
	}

	fence_event[m+1] = {INF, INF, m+1};
	xcoord[INF] = 1; ycoord[INF] = 1;
	int XIDX = 0; for(auto& [key, val] : xcoord) val = ++XIDX;
	int YIDX = 0; for(auto& [key, val] : ycoord) val = ++YIDX;

	for(int i = 1; i <= n; i++){
		buff[i].first = xcoord.lower_bound(buff[i].first)->second;
		buff[i].second = ycoord.lower_bound(buff[i].second)->second;
		event.push_back({buff[i].first, 0, buff[i].second});
	}

	for(int i = 1; i <= m+1; i++){
		fence_event[i].x = xcoord.lower_bound(fence_event[i].x)->second;
		fence_event[i].y = ycoord.lower_bound(fence_event[i].y)->second;
	}

	sort(fence_event+1, fence_event+m+2, [&](const G& a, const G& b){
		return a.y > b.y;
	}); fill_n(tree, 1818181, INF);

	for(int i = 1; i <= m+1; i++){
		int qidx = getMaxIdx(fence_event[i].x, fence_event[i].idx);
		event.push_back({qidx+1, -fence_event[i].idx, fence_event[i].y});
		event.push_back({fence_event[i].x+1, -fence_event[i].idx, -fence_event[i].y});
		boom(1, 1, m+1, qidx+1, fence_event[i].x);
		auto it = rfence.lower_bound(qidx+1);
		upd(1, 1, m+1, fence_event[i].x, fence_event[i].idx);
		while(it != rfence.end()){
			if(it->first > fence_event[i].x) break;
			auto it2 = it; it++; rfence.erase(it2);
		}
		if(fence_event[i].idx != m+1) nxt[fence_event[i].idx] = rfence.upper_bound(fence_event[i].x)->second;
		else nxt[m+1] = m+1;
		rfence[fence_event[i].x] = fence_event[i].idx;
	}

	sort(event.begin(), event.end(), [&](const Event& a, const Event& b){
		if(a.x == b.x) return a.idx < b.idx;
		return a.x < b.x;
	});
	set<pii> fence;

	for(auto& [x, idx, y] : event){
		if(idx == 0){
			int p = fence.lower_bound({y, 0})->second;
			par[p]--;
		}
		else{
			if(y > 0) fence.insert({y, -idx});
			else fence.erase({-y, -idx});
		}
	}

	stack<int> ans;
	for(int i = m; i >= 1; i--){ans.push(-par[i]); u(i, nxt[i]);}
	while(ans.size()) cout << ans.top() << '\n', ans.pop();
}