BOJ 21793 Event Hopping 2

문제 링크입니다.

문제 요약

주어진 $N$개의 indexed 반열린구간 중 겹치지 않게 $K$개를 고르는 사전 순 최소의 방법을 찾으세요.

풀이

몇 개의 구간을 고정한 상태에서 $K$개 이상의 구간을 고르는 방법이 존재하는지 판별하는 문제를 빠르게 해결할 수 있다면, 인덱스 순서대로 이를 시도해 보는 식으로 문제를 해결할 수 있습니다. 구간을 된다 판정하고 추가한 시점에서 그 구간을 뺄 일은 없으므로, 각 상황에서의 판정을 incremental하게 수행할 수 있습니다. 따라서 새로운 구간을 추가하는 경우에, 그 구간의 바로 양 옆에 있는 구간들 사이에 원래 넣을 수 있었던 최대 구간 개수 대신, 중간에 새로 추가할 구간을 고정하고 그 양 사이로 넣을 수 있는 최대 구간 개수를 계산했을 때에 여전히 총합이 $K$를 넘는지만 쭉쭉 판정해나갈 수 있으면 됩니다.

구간을 오른쪽 끝 기준 오름차순 정렬합니다. 그 뒤, 자신의 바로 다음에 올 수 있는 현재 정렬 상 가장 앞의 구간을 가리키는 함수를 생각하면 사이에 구간을 $x$에 끼울 수 있는 첫 구간을 희소 배열을 활용해 ${\cal O}(\lg N)$에 찾을 수 있습니다. 거꾸로, 시작 구간과 끝 구간이 주어졌을 때, 맨 오른쪽 구간이 주어진 끝 구간과 겹치거나 벗어나지 않도록 하는 최대 구간 개수 역시 ${\cal O}(\lg N)$에 계산 가능합니다.

따라서 전체 문제를 ${\cal O}(N \lg N)$에 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e9+7;
array<ll, 3> a[101010];
int nxt[18][101010], ord[101010]; //order after sorting

vector<int> ans;
set<int> in_ans;

int getDist(int L, int R){
	int ret = 0;
	if(a[L][0] > a[R][1]) return -1;
	for(int bit = 16; bit >= 0; bit--) if(a[nxt[bit][L]][0] <= a[R][1]) ret += (1<<bit), L = nxt[bit][L];
	return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, k; cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i][1] >> a[i][0], a[i][2] = i;
	a[0] = {1, 0, 0}; a[n+1] = {INF+1, INF, n+1};
	sort(a+1, a+n+1); for(int i = 0; i <= n+1; i++) ord[a[i][2]] = i;
	for(int L = 0, R = 1; R <= n+1; R++) while(L < R && a[L][0] <= a[R][1]) nxt[0][L++] = R;
	nxt[0][n+1] = n+1;
	for(int bit = 1; bit <= 16; bit++) for(int i = 0; i <= n+1; i++) nxt[bit][i] = nxt[bit-1][nxt[bit-1][i]];
	if(getDist(0, n+1) < k) return !(cout << -1);
	in_ans.insert(0); in_ans.insert(n+1); int mx = getDist(0, n+1);
	for(int i = 1; i <= n; i++){
		int now = ord[i]; int L = *--in_ans.lower_bound(now), R = *in_ans.lower_bound(now);
		int dL = getDist(L, now), dR = getDist(now, R);
		if(dL < 0 || dR < 0) continue;
		int tmp = -getDist(L, R)+getDist(L, now)+getDist(now, R)+1; if(mx+tmp >= k){
			ans.push_back(i); in_ans.insert(now); mx += tmp;
		}
	}
	for(int i = 0; i < k; i++) cout << ans[i] << '\n';
}