백준17704 Matryoshka

작성일 | In

문제 링크

  • http://icpc.me/17704

문제 출처

  • 2015/2016 JOISC Day1 1번

사용 알고리즘

  • 세그먼트 트리
  • 스위핑
  • DP

시간복잡도

  • $O((N+Q) \log (N+Q))$

풀이

$N$개의 점 $(X_i, Y_i)$가 주어지고 쿼리로 $(A, B)$가 주어지면, $X_i \geq A \land Y_i \leq B$인 점들만 고려했을 때 오른쪽 위로 strict하게 올라가는 minimum path cover의 크기를 구하는 문제입니다.
poset에서 minimum path cover의 크기는 maximum anti chain의 크기와 같습니다. 이 문제에서 anti chain은 $X_i \leq X_j \land Y_i \geq Y_j$를 만족하는 경로입니다. 이런 꼴의 경로 중 가능한 길이의 최댓값을 구하면 됩니다.

부등호 방향이 다르면 보기 싫으니까 $y$좌표를 뒤집어서 통일시킵니다. 쿼리로 $(A, B)$가 주어졌을 때 $(A, B)$ 기준 1사분면 또는 축에 있는 점들 중 오른쪽 위로 monotone하게 올라가는 LIS를 구하는 문제가 됩니다.
오른쪽 위로 올라가는 경로 대신 왼쪽 아래로 내려가는 경로를 생각해 봅시다. 이런 형식의 DP는 세그먼트 트리를 들고 $(y, x)$ 내림차순으로 스위핑하면서 계산할 수 있습니다.
쿼리는 $[A, \infty]\times [B, \infty]$ 구간에서의 2차원 최댓값 쿼리라고 생각할 수 있지만 2차원 쿼리를 처리하는 것은 귀찮습니다. 따라서 그냥 쿼리를 오프라인으로 입력받은 다음, DP 계산할 때 스위핑하면서 같이 정답을 구하는 것이 편합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 19;

struct Event{
    int x, y, i;
    Event() = default;
    Event(int x, int y, int i) : x(x), y(y), i(i) {}
    bool operator < (const Event &e) const {
        return make_tuple(y, x, -i) > make_tuple(e.y, e.x, -e.i);
    }
};

int N, Q, R[SZ], T[SZ<<1];
vector<int> X, Y;
vector<Event> E;

void Update(int x, int v){
    for(x|=SZ; x; x>>=1) T[x] = max(T[x], v);
}

int Query(int l, int r){
    int res = 0;
    for(l|=SZ, r|=SZ; l<=r; l/=2, r/=2){
        if(l & 1) res = max(res, T[l++]);
        if(~r & 1) res = max(res, T[r--]);
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; E.reserve(N+Q); X.reserve(N+Q); Y.reserve(N+Q);
    for(int i=1,x,y; i<=N; i++) cin >> x >> y, E.emplace_back(x,-y,0);
    for(int i=1,x,y; i<=Q; i++) cin >> x >> y, E.emplace_back(x,-y,i);
    for(const auto &[x,y,i] : E) X.push_back(x), Y.push_back(y);
    sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
    sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());
    for(auto &[x,y,i] : E){
        x = lower_bound(X.begin(), X.end(), x) - X.begin() + 1;
        y = lower_bound(Y.begin(), Y.end(), y) - Y.begin() + 1;
    }
    sort(E.begin(), E.end());
    for(const auto &[x,y,i] : E){
        if(i == 0) Update(x, Query(x, SZ-1) + 1);
        else R[i] = Query(x, SZ-1);
    }
    for(int i=1; i<=Q; i++) cout << R[i] << "\n";
}