4012번: 컨벤션 센터

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


$O(n\lg n)$

개구간 (l,r)에 컨벤션 센터를 이용할 수 있는 단체의 최대 개수 f(l,r)을 빠르게 구할 수 있다고 해보자.
그럼 1번 단체부터 차례대로 스케줄에 넣어 보면서 최적해를 유지하는지 빠르게 판단할 수 있다.
(스케줄 상 두 단체 사이 구간을 파악하는 일련의 연산은 map, set을 활용하여 해결할 수 있다.)

<f(l,r) 구하는 방법>
먼저, 단체를 회의 시작시간을 기준으로 오름차순 정렬하자.
x번 단체 바로 앞에 회의가 진행되었을 경우, 그 단체는 x번 단체 회의 시작 이전에 회의가 끝난 단체 중 시작 시간이 가장 늦은 단체여야 유리하다.
이러한 성질을 이용하여
dp[x][i]: x번 단체의 2^i번째 이전 단체
인 sparse table을 만들 수 있다.
그럼 r 전에 끝난 단체 중 가장 늦게 시작한 단체 p를 찾은 뒤
p의 2^i 이전 단체가 l 이후에 시작했는지 여부에 따라 p를 옮겨가며 카운트 하면 f(l,r)을 $O(\lg n)$에 구할 수 있다.

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int MXN = 2e5;
int n, dp[MXN + 1][18], top = 1;
pair<int, int> stk[MXN + 1], p[MXN + 1], s[MXN + 1], e[MXN + 1];
int f(int l, int r) {
    int x = (lower_bound(stk, stk + top, make_pair(r, 0)) - 1)->second, ret = 1;
    if (p[x].first <= l) return 0;
    for (int i = 17; i >= 0; i--) if (p[dp[x][i]].first > l) x = dp[x][i], ret += 1 << i;
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].first, &p[i].second);
        s[i] = { p[i].first,i };
        e[i] = { p[i].second,i };
    }
    sort(s + 1, s + 1 + n);
    sort(e + 1, e + 1 + n);
    for (int i = 1, j = 1, prv = 0; i <= n; i++) {
        for (; e[j].first < s[i].first; j++) if (p[prv].first < p[e[j].second].first) prv = e[j].second;
        while (stk[top - 1].first >= p[s[i].second].second) top--;
        stk[top++] = { p[s[i].second].second,s[i].second };
        dp[s[i].second][0] = prv;
        for (int j = 1; j < 18; j++) dp[s[i].second][j] = dp[dp[s[i].second][j - 1]][j - 1];
    }
    printf("%d\n", f(0, 2e9));
    map<int, int> mp;
    mp[0] = 0;
    mp[2e9] = 2e9;
    for (int i = 1; i <= n; i++) {
        auto l = mp.lower_bound(p[i].first), r = l--;
        if (l->second < p[i].first&&p[i].second < r->first
            &&f(l->second, r->first) == f(l->second, p[i].first) + 1 + f(p[i].second, r->first)) {
            printf("%d ", i);
            mp[p[i].first] = p[i].second;
        }
    }
    return 0;
}