백준 12795 - 반평면 땅따먹기 (C++)

문제

• 문제 링크

  
   BOJ 12795 - 반평면 땅따먹기 
  

• 문제 요약

$Li-Chao$ $Tree$

• 제한

TL : $2$ sec, ML : $128$ MB




$1 ≤ Q ≤ 200,000$

$|a| ≤ 1,000,000$

$|b|, |x| ≤ 1,000,000,000,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 자료 구조(data structures)
• 볼록 껍질을 이용한 최적화(convex hull trick)

풀이

리차오 트리 그 자체인 문제다.

나는 jhnah917님의 글 에서 리차오 트리를 공부했는데, 되게 참신한 자료 구조라고 생각한다.
노드마다 직선의 방정식을 박을 줄이야..

여튼 $f(x) = ax + b$의 형태에서 $a$와 $b$가 직접적으로 주어진다.
따라서, 동적 노드마다 절반 이상에서 최댓값을 갖는 직선을 취하고 최댓값 쿼리를 날려주면 된다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
struct L
{
    ll p, q;
    inline ll f(ll x) { return p * x + q; }
};
struct Node
{
    ll l, r, s, e;
    L ln;
};
vector <Node> T;
ll q, o, i, j, M(-2e18);
 
void push(L q, ll n)
{
    ll s(T[n].s), e(T[n].e), m((s + e) >> 1); L p = T[n].ln;
    if (p.f(s) > q.f(s)) swap(p, q);
    if (p.f(e) <= q.f(e)) { T[n].ln = q; return; }
    if (p.f(m) < q.f(m))
    {
        T[n].ln = q;
        if (!~T[n].r)
            T[n].r = T.size(), T.push_back({ -1, -1, m + 1, e, { 0, M } });
        push(p, T[n].r);
        return;
    }
    T[n].ln = p;
    if (!~T[n].l)
        T[n].l = T.size(), T.push_back({ -1, -1, s, m, { 0, M } });
    push(q, T[n].l);
}
ll Q(ll x, ll n) { return !~n ? M : max(T[n].ln.f(x), Q(x, ((x << 1) <= T[n].s + T[n].e ? T[n].l : T[n].r))); }
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    T.push_back({ -1, -1, (ll)-1e12, (ll)1e12, {0, M} });
    for (cin >> q; q--;)
    {
        cin >> o;
        if (o & 1) cin >> i >> j, push({ i, j }, 0);
        else cin >> i, cout << Q(i, 0) << '\n';
    }
}

comment

끝