백준12876 반평면 땅따먹기 2

작성일 | In

문제 링크

  • http://icpc.me/12876

사용 알고리즘

  • CHT
  • convex Hull
  • offline dynamic connectivity

시간복잡도

  • $O(N log^2 N)$

풀이

offline dynamic connectivity problem 에서는 간선의 수명을 구한 다음, 세그먼트 트리로 관리해주는 방식으로 문제를 해결했습니다.
비슷한 방법으로, 이 문제에서는 직선의 수명을 구해서 세그먼트 트리로 관리하며 오프라인으로 처리할 것입니다.
직선의 수명 구간 안에 완전히 포함되는 노드에만 직선을 넣어주면 됩니다.

각 정점에서 CHT를 관리해주는 조금 이상한 세그먼트 트리를 만들 것입니다.
직선들을 모두 세그먼트 트리에 넣어준 뒤, graham scan과 유사한 방법으로 직선들을 정렬해주면 됩니다.
전처리를 모두 했다면, 각 쿼리에 대한 답은 삼분탐색 등을 이용해 구할 수 있습니다.

전체 코드

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#pragma GCC optimize('Ofast')
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

inline ll f(p line, ll x){ //ax+b
    return line.x * x + line.y;
}

vector<p> tree[1010101];

int ccw(p a, p b, p c){
    ll res = a.x*b.y + b.x*c.y + c.x*a.y;
    res -= b.x*a.y + c.x*b.y + a.x*c.y;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}

void update(int node, int s, int e, int l, int r, p v){ //각 시간이 리프노드인 세그트리
    if(r < s || e < l) return;
    if(l <= s && e <= r){ //완전히 포함되면 push
        tree[node].push_back(v);
        return;
    }
    int m = s + e >> 1;
    update(node << 1, s, m, l, r, v);
    update(node << 1 | 1, m+1, e, l, r, v);
}

vector<p> hull;
void makeCHT(int node){ //세그 트리의 각 정점의 직선으로 볼록껍질 만듬 -> 쿼리 처리할 때 삼분탐색
    sort(tree[node].begin(), tree[node].end(), [&](p &a, p &b){
        return make_pair(a.x, -a.y) < make_pair(b.x, -b.y);
    });
    hull.clear();
    int pv = -2e9;
    for(auto i : tree[node]){
        if(i.x == pv) continue;
        pv = i.x;
        while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), i) > 0){
            hull.pop_back();
        }
        hull.push_back(i);
    }
    tree[node] = hull;
}

void dfs(int node, int s, int e){ //offline
    makeCHT(node);
    if(s ^ e){
        int m = s + e >> 1;
        dfs(node << 1, s, m);
        dfs(node << 1 | 1, m+1, e);
    }
}

ll _query(int node, ll x){ //삼분 탐색 or 기울기로 이분탐색해서 최댓값
    if(tree[node].empty()) return -5e18;
    int l = 0, r = tree[node].size()-1;
    while(l < r){
        int m = l + r >> 1;
        if(f(tree[node][m], x) < f(tree[node][m+1], x)) l = m + 1;
        else r = m;
    }
    return f(tree[node][l], x);
}

ll query(int node, int s, int e, int t, ll x){ //time, ax+b
    ll ret = _query(node, x);
    if(s == e) return ret;
    int m = s + e >> 1;
    if(t <= m) ret = max(ret, query(node << 1, s, m, t, x));
    else ret = max(ret, query(node << 1 | 1, m+1, e, t, x));
    //cout << "time : " << t << " / " << node << " " << s << " " << e << " / " << ret << "\n";
    return ret;
}

struct asdf{
    ll s, e, a, b;
};

int cnt[303030]; //time slice
int chk[303030]; //삽입된 직선이 제거가 됐었나?
p line[303030]; //어떤 직선이 삽입되었는가?
vector<asdf> v; //그 직선의 life time은?
int qry[303030]; //각 시간대에 주어진 쿼리들

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q; cin >> q;
    for(int i=1; i<=q; i++){
        int op; cin >> op;
        if(op == 1){
            cin >> line[i].x >> line[i].y; chk[i] = 1;
        }else if(op == 2){
            int t; cin >> t;
            v.push_back({cnt[t]+1, cnt[i-1], line[t].x, line[t].y});
            chk[t] = 0;
        }else{
            cin >> qry[i]; cnt[i]++;
        }
        cnt[i] += cnt[i-1];
    }
    if(cnt[q] == 0) return 0;
    for(int i=1; i<=q; i++){ //제거 안한 직선들의 제거 시점 강제로 배정
        if(chk[i]){
            v.push_back({cnt[i]+1, cnt[q], line[i].x, line[i].y});
        }
    }
    for(auto i : v){
        update(1, 1, cnt[q], i.s, i.e, {i.a, i.b});
    }
    dfs(1, 1, cnt[q]);
    for(int i=1; i<=q; i++){
        if(cnt[i] ^ cnt[i-1]){ //쿼리가 있으면
            ll now = query(1, 1, cnt[q], cnt[i], qry[i]);
            if(now <= -5e18) cout << "EMPTY\n";
            else cout << now << "\n";
        }
    }
}