[Algorithm] C++ 백준 12876번: 반평면 땅따먹기 2

문제

링크: https://www.acmicpc.net/problem/12876
요약: 공집합에서 시작해 연산 순서대로 (1) 직선 (a, b) 추가, (2) 특정 추가 연산으로 넣었던 직선 제거, (3) 주어진 x에 대해 남아있는 모든 직선 중 ax + b의 최댓값을 출력한다. 집합이 비어 있으면 EMPTY를 출력한다.

제한/스펙

1 ≤ N ≤ 300,000 (연산 개수)
-1e9 ≤ a, b, x ≤ 1e9
출력 시 공집합이면 EMPTY, 아니면 최댓값(정수)

입출력 형식/예제

예제 입력 1

예제 출력 1

1
2
3
4
EMPTY
5
99
5

접근 개요(아이디어 스케치)

핵심 모델: 각 원소는 직선 y = a x + b. 질의는 고정된 x에서의 최대값.
난점: 직선이 중간에 삭제되므로 단순 Li Chao Tree의 “온라인 추가만” 구조로는 제거를 처리하기 어렵다.
오프라인 전환: 각 추가 연산의 “활성 시간 구간” [start, end)을 복원한다. 이 구간에 해당하는 노드에 직선을 보관하는 “시간 축 세그먼트 트리”를 만든다.
DFS 진행: 세그먼트 트리 DFS를 돌며 현재 노드 구간에 해당하는 직선들을 Li Chao Tree에 삽입한다. 리프(하나의 시간점)에서 질의를 평가하고 상위로 되돌아갈 때 Li Chao Tree 상태를 롤백한다.
Li Chao 롤백: 노드별로 바뀐 라인의 이전 값을 스택에 저장해 되돌릴 수 있게 구현하면, 시간 축을 따라 직선의 삽입/제거 효과를 모사할 수 있다.

flowchart TD
  A[연산 파싱] --> B[추가 연산의 start/end 계산]
  B --> C[시간 세그먼트 트리에 (라인, 구간) 배치]
  C --> D[DFS]
  D --> E[노드에 속한 라인들 Li Chao에 삽입]
  E --> F{리프?}
  F -- 예 --> G[해당 시간의 질의들 평가]
  F -- 아니오 --> H[좌/우 자식 DFS]
  H --> I[리턴 시 Li Chao 롤백]

알고리즘 설계

상태/자료구조:
- 시간 세그먼트 트리: 노드마다 그 구간 전체에서 “활성인 직선” 목록 저장
- Li Chao Tree: 구간 최대값 질의용. 각 갱신 시 이전 라인을 기록해 롤백 지원
절차:
1. 입력을 한 번 훑어 각 추가 연산의 종료 시점(삭제 시각, 없으면 n+1)을 결정
2. [start, end) 구간에 해당 직선을 세그먼트 트리에 배치
3. DFS로 세그먼트 트리를 순회하며 각 노드 직선을 Li Chao에 추가, 리프 시간에 모인 질의를 모두 평가
4. 자식 방문 종료 후 Li Chao를 롤백하여 상위 상태 복원
정당성(요지): 각 시간 t에서 활성인 직선 집합은 해당 리프까지의 경로에 추가된 직선들의 합집합과 정확히 일치한다. Li Chao Tree는 “최댓값” 유지에 적합하고, 롤백은 상위 구간의 상태를 보존한다.

복잡도

시간: 각 직선이 O(log N)개 노드에 배치되고, Li Chao 삽입/질의가 O(log X) → 전체 O(N log N log X)
공간: 세그먼트 트리의 버킷 합 O(N log N) (실제 상수는 낮음), Li Chao 노드 풀 O(삽입 수)

구현 (C++)

 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
static const ll X_MIN = -1000000000LL;
static const ll X_MAX =  1000000000LL + 1; // [X_MIN, X_MAX)
static const long long NEG_INF = (long long)-4e18;

struct Line { ll m, b; }; // y = m x + b

struct LiChao {
    struct Node {
        Line ln; int lc, rc; // child indices
        Node() : ln({0, NEG_INF}), lc(0), rc(0) {}
    };
    vector<Node> pool; int root = 0;
    vector<pair<int, Line>> history; // (index, old line)

    LiChao() { pool.reserve(1<<22); pool.push_back(Node()); }
    int new_node(){ pool.push_back(Node()); return (int)pool.size()-1; }
    inline __int128 f(const Line& L, ll x) const { return (__int128)L.m * x + L.b; }

    void add_line(Line nw){ add_line(root, X_MIN, X_MAX, nw); }
    void add_line(int &n, ll l, ll r, Line nw){
        if(n==0) n = new_node();
        int idx = n; ll mid = (l + r) >> 1;
        Line lo = pool[idx].ln, hi = nw;
        bool leftBetter = f(hi, l) > f(lo, l);
        bool midBetter  = f(hi, mid) > f(lo, mid);
        if(midBetter) swap(lo, hi);
        if(pool[idx].ln.m != lo.m || pool[idx].ln.b != lo.b){
            history.emplace_back(idx, pool[idx].ln);
            pool[idx].ln = lo;
        }
        if(r - l == 1) return;
        if(leftBetter != midBetter) add_line(pool[idx].lc, l, mid, hi);
        else                        add_line(pool[idx].rc, mid, r, hi);
    }

    ll query(ll x) const { return root? (ll)query_rec(root, X_MIN, X_MAX, x) : NEG_INF; }
    __int128 query_rec(int n, ll l, ll r, ll x) const{
        if(n==0) return (__int128)NEG_INF;
        const Node &nd = pool[n]; __int128 res = f(nd.ln, x);
        if(r - l == 1) return res; ll mid = (l + r) >> 1;
        if(x < mid) return max(res, query_rec(nd.lc, l, mid, x));
        return max(res, query_rec(nd.rc, mid, r, x));
    }

    void rollback(size_t checkpoint){
        while(history.size() > checkpoint){ auto [idx, oldLine] = history.back(); history.pop_back(); pool[idx].ln = oldLine; }
    }
};

struct SegmentTree {
    int n; vector<vector<Line>> bucket; // 1..n+1 구간
    SegmentTree(int n_) : n(n_), bucket(4*(n_+5)) {}
    void add_range(int node, int L, int R, int ql, int qr, const Line &ln){
        if(qr<=L || R<=ql) return; if(ql<=L && R<=qr){ bucket[node].push_back(ln); return; }
        int mid=(L+R)>>1; add_range(node<<1, L, mid, ql, qr, ln); add_range(node<<1|1, mid, R, ql, qr, ln);
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;

    vector<int> type(n+1); vector<long long> A(n+1), B(n+1), X(n+1);
    vector<int> start(n+1, -1), fin(n+1, -1);
    vector<vector<pair<long long,int>>> queriesAt(n+2);
    int qcnt=0;
    for(int i=1;i<=n;++i){
        cin>>type[i];
        if(type[i]==1){ cin>>A[i]>>B[i]; start[i]=i; fin[i]=n+1; }
        else if(type[i]==2){ int idx; cin>>idx; fin[idx]=i; }
        else { cin>>X[i]; queriesAt[i].push_back({X[i], qcnt++}); }
    }

    SegmentTree seg(n+1);
    for(int i=1;i<=n;++i){ if(type[i]==1){ int L=start[i], R=fin[i]; if(L<R) seg.add_range(1,1,n+1,L,R, Line{A[i],B[i]}); } }

    vector<string> ans(qcnt); LiChao lichao; int active=0;
    function<void(int,int,int)> dfs = [&](int node,int L,int R){
        size_t cp = lichao.history.size(); int saved=active;
        for(const auto &ln: seg.bucket[node]){ lichao.add_line(ln); ++active; }
        if(L+1==R){
            for(auto &q: queriesAt[L]){ if(active==0) ans[q.second] = "EMPTY"; else ans[q.second] = to_string(lichao.query(q.first)); }
        } else {
            int mid=(L+R)>>1; dfs(node<<1,L,mid); dfs(node<<1|1,mid,R);
        }
        lichao.rollback(cp); active=saved;
    };
    dfs(1,1,n+1);

    for(int i=0;i<qcnt;++i) cout<<ans[i]<<'\n';
    return 0;
}