[BOJ 12876] 반평면 땅따먹기 2, 그리고 Lichao Tree

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

 

일차함수 $y=a_ix+b_i$들의 최댓값에 대해 생각해보자.

 

잘 생각해보면, 최댓값을 이루는 직선들의 기울기는 $x$좌표가 증가하며 단조증가함을 알 수 있다.

만약 단조증가하지 않는다면, 기울기가 감소하게 된 직선의 이전의 직선이 더 큰 함수값을 가지므로 모순이 된다.

 

따라서, CHT를 짜듯이 된다. 다만 입력으로 들어오는 직선의 기울기의 단조성이 없고, 삽입과 삭제가 있다. 때문에 적당한 이분탐색과 set으로 직선들을 관리해야 한다.

 

하지만 우리에게는 더 무지성을 지향할 수 있는 자료구조가 있다. 바로 리차오 세그먼트 트리이다.

어떤 구간의 중앙값에서 가장 함숫값이 큰 함수에 대해 생각하자. 이를 그 구간을 대표하는 직선이라고 하자.

구간을 대표하는 직선과 다른 직선을 비교해보자. 잘 생각해보면 구간을 대표하는 직선이 어떤 임의의 직선과 비교했을 때 적어도 절반의 구간에서는 더 크다는 것을 알 수 있다. 때문에 어떤 직선이 추가되었을 때, 그 직선이 대표할 수 있는 구간을 계속해서 찾아 업데이트 해주면, 결국 어떤 점 $x$에서 함수의 최댓값은 $x$를 포함하는 구간들을 대표하는 직선들로 계산한 함숫값들 중 최댓값이 된다. 만약 원래 대표하던 직선이 바뀌는 경우 원래의 직선으로 다시 내려가며 업데이트하면 된다. 이 때 직선들의 갯수는 $x$의 범위를 $X$라 할 때 $O(\log X)$이므로, 적당한 시간에 계산할 수 있다.

 

하지만 리차오 세그먼트 트리에서도 직선의 삭제는 online으로 (내가 아는 선에서는) 불가능하다. 때문에 삽입과 삭제 쿼리를 offline으로 관리하는데, 이 때 세그먼트트리처럼 시간을 관리한다. 즉, 어떤 직선이 유효한 시간이 $[s, e]$일 때 $[s, e]$를 덮는 세그먼트트리 노드(이면서 리차오 세그먼트 트리)들에만 해당 직선을 업데이트 하는 것이다. 그러면 시간복잡도가 $O(Q\log{Q}\log{X})$가 되어 문제를 풀 수 있다.

 

다만 리차오 세그먼트 트리를 최적화하지 않으면 MLE, TLE가 나기 쉽상이므로 잘 구현하도록 하자. vector를 이용해서 구현할 수도 있고 포인터를 이용해서 구현할 수 있으나 중요한 점은 구간을 대표하는 직선이 새로 생겼을 때 더 이상 깊이 들어가지 않는 것이다. (사실 이렇게 안 해도 log가 보장되기는 할텐데 메모리나 시간이나 상수가 거의 4배 차이날 것같다.)

 

코드

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair <int, ll> pii;
typedef pair <ll, ll> pll;

const int MAX = 303030;
const int INF = (int)1e9;
const ll LINF = (ll)9e18;


struct LiChaoSegmentTree { // [s, e)
    struct Node {
        Node *l = nullptr, *r = nullptr;
        pll val;
        Node(pll val) : val(val) {}
    } *tree = nullptr;

    ll cal(pll l, ll x) {
        return l.fi * x + l.se;
    }
    void add_line(Node *node, pll val, ll s = -INF, ll e = INF + 1) { // modify s & e
        ll m = s + e >> 1;
        bool left = cal(val, s) > cal(node->val, s); // > if max
        bool mid = cal(val, m) > cal(node->val, m); // > if max
        if(mid) swap(val, node->val);
        if(e == s + 1) return;
        if(left != mid) {
            if(!node->l) node->l = new Node(val);
            else add_line(node->l, val, s, m);
        }
        else {
            if(!node->r) node->r = new Node(val);
            else add_line(node->r, val, m, e);
        }
    }

    void add(pll val) {
        if(!tree) tree = new Node(val);
        else add_line(tree, val);
    }

    ll query(Node *node, ll x, ll s = -INF, ll e = INF + 1) { // modify s & e
        if(!node) return -LINF; // -LINF if max
        ll m = s + e >> 1;
        if(e == s + 1) return cal(node->val, x);
        if(x < m) return max(cal(node->val, x), query(node->l, x, s, m));
        else return max(cal(node->val, x), query(node->r, x, m, e));
    }

    ll query(ll x) {
        if(!tree) return -LINF; // -LINF if max
        return query(tree, x);
    }
};

class SEG {
    vector <LiChaoSegmentTree> tree;
    int n;
public :
    void Init(int N) {
        n = N;
        tree.resize(4*n);
    }

    void update(int l, int r, pii val, int s, int e, int node = 1) {
        if(s > r || e < l) return;
        if(s >= l && e <= r) {
            tree[node].add(val);
            return;
        }
        int m = (s + e) / 2;
        update(l, r, val, s, m, node * 2);
        update(l, r, val, m + 1, e, node * 2 + 1);
    }

    void Update(int l, int r, pii val) {
        update(l, r, val, 1, n);
    }

    ll cal_max(int k, int x, int s, int e, int node = 1) {
        if(k == 0) return -LINF;
        if(s == e) return tree[node].query(x);
        int m = (s + e) / 2;
        if(k <= m) return max(tree[node].query(x), cal_max(k, x, s, m, node * 2));
        else return max(tree[node].query(x), cal_max(k, x, m + 1, e, node * 2 + 1));
    }

    ll Cal_max(int k, int x) {
        return cal_max(k, x, 1, n);
    }
} ST;

pii line[MAX];
bool chk[MAX];
vector <pii> pt;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;
    ST.Init(n);
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        if(t == 1) {
            cin >> line[i].fi >> line[i].se;
            chk[i] = true;
        }
        if(t == 2) {
            int x;
            cin >> x;
            ST.Update(x, i, line[x]);
            chk[x] = false;
        }
        if(t == 3) {
            int x;
            cin >> x;
            pt.eb(i, x);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(chk[i]) ST.Update(i, n, line[i]);
    }
    for(auto i : pt) {
        ll ans = ST.Cal_max(i.fi, i.se);
        if(ans == -LINF) cout << "EMPTY" << '\n';
        else cout << ans << '\n';
    }
}