오랜만에 글을 쓴다.

ploffer11이다.

탈알고 한다면서 씹덕 알고 하고 있으니 얘가 다시 알창이 됬나 오해할 수 있는데, 오히려 취미로 게임하듯 하니까 난이도 있는 알고리즘만 하게 되서 그렇다.

아무튼 퍼시스턴트 리차오 트리와 오프라인 리차오 트리가 뭐냐?

일단 리차오 트리 모르는 사람은 그것부터 배우고 읽길

Offline LiChao Tree

오프라인 리차오 트리는 다음과 같은 쿼리에서 쓰일 수 있다

Query

1. f(x) = ax + b 를 추가
2. 임의의 x에 대해 max(f(x)) 구하기
3. 내가 i번째 연산으로 추가한 직선 삭제

Description

즉 임의의 삭제 쿼리를 처리할 수 있는 리차오 트리인데, 온라인으로는 불가능(일단 내가 인터넷에서는 못찾음)하기 때문에 Offline Dynamic Connectivity와 같은 테크닉을 사용한다. 각 직선의 Lift Time을 [l, r]로 전처리 한 다음(삭제되지 않으면 쿼리 개수가 r이 됨) 쿼리들만 쫙 모아서 자기 쿼리 번호에 살아있는 직선들에 대해서 max(f(x))를 하면 된다.

Koosaga님의 세그먼트트리 스타일코드가 이뻐서 그걸 참조해 오프라인 리차오 트리를 완성했다.

Code

class OfflineLiChaoTree
{
private:
    class LiChaoTree
    {
    private:
        struct Line
        {
            ll a, b;
            Line(ll a, ll b) : a(a), b(b) {}

            ll f(ll x)
            {
                return (ll)a * x + b;
            }
        };

        struct Node
        {
            int l, r;
            int xl, xr;
            Line line;
        };

        vector<Node> tree;

    public:
        int s = -2e9, e = 2e9;
        LiChaoTree()
        {
            tree.push_back({-1, -1, s, e, Line(0, -INF)});
        }

        void add_line(Line new_line, int i = 0)
        {
            int xl = tree[i].xl, xr = tree[i].xr;
            int xm = ((ll)xl + xr) >> 1;

            Line low = tree[i].line, high = new_line;

            if (low.f(xl) >= high.f(xl))
                swap(low, high);

            if (low.f(xr) <= high.f(xr))
            {
                tree[i].line = high;
                return;
            }

            else if (low.f(xm) <= high.f(xm))
            {
                tree[i].line = high;
                if (tree[i].r == -1)
                {
                    tree[i].r = tree.size();
                    tree.push_back({-1, -1, xm + 1, xr, Line(0, -INF)});
                }
                add_line(low, tree[i].r);
            }
            else
            {
                tree[i].line = low;
                if (tree[i].l == -1)
                {
                    tree[i].l = tree.size();
                    tree.push_back({-1, -1, xl, xm, Line(0, -INF)});
                }
                add_line(high, tree[i].l);
            }
        }

        ll query(ll x, int i = 0)
        {
            if (i == -1)
                return -INF;
            int xl = tree[i].xl, xr = tree[i].xr;
            int xm = ((ll)xl + xr) >> 1;
            if (x <= xm)
                return max(tree[i].line.f(x), query(x, tree[i].l));
            else
                return max(tree[i].line.f(x), query(x, tree[i].r));
        }

        Line query2(ll x, int i = 0)
        {
            if (i == -1)
                return Line(0, -INF);
            int xl = tree[i].xl, xr = tree[i].xr;
            int xm = ((ll)xl + xr) >> 1;
            if (x <= xm)
            {
                Line line = query2(x, tree[i].l);
                if (line.f(x) > tree[i].line.f(x))
                    return line;
                else
                    return tree[i].line;
            }
            else
            {
                Line line = query2(x, tree[i].r);
                if (line.f(x) > tree[i].line.f(x))
                    return line;
                else
                    return tree[i].line;
            }
        }
    };

    vector<LiChaoTree> tree;
    vector<tuple<int, int, ll, ll>> q;
    vector<pair<int, ll>> q2;
    vector<ll> ans;
    int q_idx;

    void insert(int i, int s, int e, int l, int r, pll value)
    {
        if (r < s || e < l)
            return;

        if (l <= s && e <= r)
        {
            tree[i].add_line({value.first, value.second});
            return;
        }

        int m = ((ll)s + e) >> 1;
        insert(2 * i, s, m, l, r, value);
        insert(2 * i + 1, m + 1, e, l, r, value);
    }

    ll query(int i, int s, int e, int idx, ll x)
    {
        if (!(s <= idx && idx <= e))
            return -INF;

        if (s == e)
            return tree[i].query(x);

        int m = ((ll)s + e) >> 1;
        return max({tree[i].query(x), query(2 * i, s, m, idx, x), query(2 * i + 1, m + 1, e, idx, x)});
    }

public:
    OfflineLiChaoTree(int q) : q_idx(0), tree(4 * q) {}

    int add_line(ll a, ll b)
    {
        q.push_back({++q_idx, -1, a, b});
        return q.size() - 1;
    }

    void delete_line(int i)
    {
        get<1>(q[i]) = ++q_idx;
    }

    void query(ll x)
    {
        q2.push_back({++q_idx, x});
    }

    vector<ll> get_ans()
    {
        for (auto [l, r, a, b] : q)
            insert(1, 1, q_idx, l, (r == -1 ? q_idx : r), {a, b});

        for (auto [idx, x] : q2)
            ans.push_back(query(1, 1, q_idx, idx, x));

        return ans;
    }
};

Persistent LiChao Tree

퍼시스턴트 리차오트리는 언뜻 보면 오프라인 리차오 트리의 하위호환처럼 보인다. 그러나 이친구는 온라인이라서 오프라인 리차오 트리가 해결하지 못하는 쿼리를 할 수 있다.

Query

1. f(x) = ax + b 를 추가
2. 임의의 x에 대해 max(f(x)) 구하기
3. 가장 최근에 삽입한 직선을 삭제

Description

놀랍게도 삭제쿼리가 3번쿼리에 한정되어 있을 경우, 오프라인이 아니라 온라인으로도 처리 가능하다

그래서 퍼시스턴트 리차오 트리는 어떻게 짜느냐. 중요한건 3번 쿼리를 어떻게 처리하냐는 건데, 잘 생각해보면 직선을 추가하는 쿼리에 추가되거나 변경되는 노드는 log(수의 범위) 개 밖에 안된다. 이런 발상은 Persistent Segment Tree와 똑같은데, Persistent LiChao Tree는 그냥 어떤 노드가 변경되면 변경 전 정보를 담아두다가 3번쿼리가 들어올때마다 마지막 변경 전으로 되돌리면 된다.

Code

class PersistentLiChaoTree
{
private:
    struct Line
    {
        int idx;
        ll a, b;
        Line(ll a, ll b, int idx = -1) : a(a), b(b), idx(idx) {}
        Line() {}
        ll f(ll x)
        {
            return a * x + b;
        }
    };

    struct Node
    {
        int l, r;
        ll xl, xr;
        Line line;
        Node(int l, int r, ll xl, ll xr, Line line) : l(l), r(r), xl(xl), xr(xr), line(line) {}
    };

    struct Info
    {
        int l, r;
        ll a, b;
    };

    vector<Node> tree;

    map<int, vector<pair<int, Info>>> change;
    ll s = -2e9, e = 2e9;
    int idx = 0;

    void add_line(Line new_line, int i = 0)
    {
        ll xl = tree[i].xl, xr = tree[i].xr;
        ll xm = (xl + xr) >> 1;

        change[idx].push_back({i, {tree[i].l, tree[i].r, tree[i].line.a, tree[i].line.b}});

        Line low = tree[i].line, high = new_line;

        if (low.f(xl) >= high.f(xl))
            swap(low, high);

        if (low.f(xr) <= high.f(xr))
        {
            tree[i].line = high;
            return;
        }

        else if (low.f(xm) <= high.f(xm))
        {
            tree[i].line = high;
            if (tree[i].r == -1)
            {
                tree[i].r = tree.size();
                tree.push_back({-1, -1, xm + 1, xr, Line(0, -INF)});
            }
            add_line(low, tree[i].r);
        }
        else
        {
            tree[i].line = low;
            if (tree[i].l == -1)
            {
                tree[i].l = tree.size();
                tree.push_back({-1, -1, xl, xm, Line(0, -INF)});
            }
            add_line(high, tree[i].l);
        }
    }

public:
    PersistentLiChaoTree()
    {
        tree.push_back({-1, -1, s, e, Line(0, -INF)});
    }

    ll query(ll x, int i = 0)
    {
        if (i == -1)
            return -INF;
        ll xl = tree[i].xl, xr = tree[i].xr;
        ll xm = (xl + xr) >> 1;
        if (x <= xm)
            return max(tree[i].line.f(x), query(x, tree[i].l));
        else
            return max(tree[i].line.f(x), query(x, tree[i].r));
    }

    void add_line(ll a, ll b)
    {
        add_line({a, b}, 0);
        idx++;
    }

    void delete_line()
    {
        for (auto &[i, info] : change[--idx])
        {
            tree[i].l = info.l;
            tree[i].r = info.r;
            tree[i].line.a = info.a;
            tree[i].line.b = info.b;
        }
        change[idx].clear();
    }
};

내가 인터넷에서 검색해본 결과 오프라인 리차오 트리와 퍼시스턴트 리차오 트리는 정보도 별로 없던데, 누군가에게 이 글이 도움이 됬기를