블로그 옮겼습니다

BOJ 3133번 코끼리 본문

Algorithm/Problem Solving

BOJ 3133번 코끼리

sgc109 2017. 8. 7. 22:13

문제 링크


N <= 10^5


N 이 주어지고 N개의 좌표가 주어진다.

두 점 (x1, y1), (x2, y2) 가 있을 때 x1 < x2 이고 y1 < y2 일 때만 (x1, y1) 에서 (x2, y2) 로 이동이 가능하다.

처음에는 아무점에서 시작할 수가 있을 때 최대로 방문할 수 있는 점의 수 K와

K개를 방문할 수 있는 경우의 수를 구하는 문제이다. 좌표의 범위는 좌표압축을 하면 되므로 딱히 상관없다.


우선 K를 구해보자. 이건 간단하다 세그트리로 LIS 를 구할 때처럼 하면 된다.

dist[i] : i 번 점까지 가장 많은 방문 수

로 두고 중간 중간 메모를 해두자.

일단 편의상 x좌표가 모두 유니크하다고 보겠다.

일단 x좌표로 점들을 정렬하고 하나씩 봐나간다. 현재 보는 점이 (xi, yi) 라면 현재 세그트리에 정보가

들어가 있는 모든 점들은 모두 x좌표가 xi 미만일 것이다. 그렇기 때문에 x좌표로 정렬하고 차례대로 봐줌으로써

x좌표의 대소관계는 자동으로 만족되는 것이다. 그렇다면 query(0, yi - 1) 를 날려 현재 특정 점으로 가는

가장 많은 방문수 x가 나오면 여기에 1을 더하면 현재 점에 도착하는 가장 많은 방문 수가 되므로

update(yi, x+1) 를 하면된다. 그리고 dist[i] = x + 1 일 것이다.

이런식으로 마지막 점까지 봐주면 최대 방문 수는 구할 수가 있다. 그리고 x좌표가 같은 점들에 대해서는

y좌표를 내림차순으로 정렬해주면 될 것이다.


그럼 이제 이 K개를 방문할 수 있는 경우의 수를 구하는 것을 생각해보자.

이 것은 세그먼트 트리의 노드에 들어가는 정보의 정의를 약간 수정함으로써 K와 동시에 계산할 수가 있다.

원래 특정 순간에 세그먼트의 특정노드에 들어가는 정보는 특정 구간의 y좌표를 갖는 점들 중에서

그 점까지 도달할 때 방문할 수 있는 점의 최대 수이다.

이 것을 pair 로 바꿔줘 보자. pair 의 첫번째 원소는 동일하다. 다만 두번째 원소는 이 수의 점을

방문하는 경우의 수의 합을 담고있다. 사실 노드의 갱신만 약간 변형해주면 간단하다.

노드를 바텀업으로 갱신을 하며 올라가는것을 상상해보자. 이전에는 좌, 우 노드 중에

큰 값을 취하는 것을 반복하며 올라갔을 것이다. 만약 좌, 우 노드의 값이 같더라도 그냥 그 같은 값으로

노드를 갱신하며 올라갔을 것이다. 만약 좌, 우 노드의 첫번째원소가 같을 때는 이전과 동일하게

첫번째 원소가 큰 pair 를 취하여 올라간다. 그런데 여기가 중요하다. 만약 좌, 우 노드의 첫번째 원소가

같다면? 두번째 원소는 좌, 우의 합을 취한다. 사실 그럼 끝이다.

마지막에 가능한 모든 y좌표보다 큰 y좌표를 L 이라고할 때 query(0, L) 쿼리를 하나 날려주면

반환되는 pair에 두 답이 모두 들어가 있을 것이다.


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
struct point{
    int x, y;
    bool operator<(const point& rhs) const{
        if(x != rhs.x) return x < rhs.x;
        return y > rhs.y;
    }
};
int N, size;
vector<int> vx, vy;
point ps[300003];
pair<int,int> t[1200003];
pair<int,int> dist[300003];
pair<int,int> merge(pair<int,int>& p1, pair<int,int>& p2){
    if(p1.first < p2.first) return p2;
    if(p1.first > p2.first) return p1;
    return {p1.first, (p1.second + p2.second) % mod};
}
void update(int pos, pair<int,int> p){
    pos += size;
    t[pos] = merge(t[pos], p);
    for(; pos > 1; pos /= 2){
        auto& par = t[pos / 2];
        auto c1 = t[pos], c2 = t[pos ^ 1];
        par = merge(c1, c2);
    }
}
pair<int,int> query(int l, int r){
    pair<int,int> ret = {-inf, 0};
    for(l += size, r += size; l <= r; l /= 2, r /= 2){
        if(l & 1) ret = merge(ret, t[l++]);
        if(~r & 1) ret = merge(ret, t[r--]);
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false),cin.tie(NULL);
    for(int i = 0 ; i < 1200000; i++) t[i] = {-inf, 0};
    cin >> N;
    for(size = 1size <= N; size *= 2);
    vx.resize(N), vy.resize(N);
    for(int i = 0 ; i < N; i++){
        int x, y;
        cin >> x >> y;
        ps[i] = {x, y};
        vx[i] = x, vy[i] = y;
    }
    sort(all(vx)), sort(all(vy));
    for(int i = 0 ; i < N; i++){
        int& x = ps[i].x, &= ps[i].y;
        x = lower_bound(all(vx), x) - vx.begin() + 1;
        y = lower_bound(all(vy), y) - vy.begin() + 1;
    }
 
    sort(ps, ps + N);
    update(0, {01});
    for(int i = 0 ; i < N; i++){
        auto p = ps[i];
        dist[i] = query(0, p.y - 1);
        dist[i].first = (dist[i].first + 1) % mod;
        update(p.y, dist[i]);
    }
    auto ans = query(0, vy.size() + 1);
 
    cout << ans.first << '\n' << ans.second;
    return 0;
}
cs


Comments