Offline Deletable Convex Hull Trick
(data-structure/cht/offline_deletable_convex_hull_trick.hpp)

• View this file on GitHub
• Last update: 2024-01-08 01:32:22+09:00
• Include: #include "data-structure/cht/offline_deletable_convex_hull_trick.hpp"

Description

直線の多重集合に対する以下のクエリをオフラインで処理する:

• 直線の追加
• 直線の削除
• $x$ における最小値の取得

Undo 可能 Li Chao tree を用いて，offline dynamic connectivity の要領でこれを実現する．

空間計算量: $O(q\log q)$

Operations

• void add(T a, T b)
  • 直線 $ax + b$ を追加する
  • 時間計算量: $O(\log q)$
• void erase(T a, T b)
  • 直線 $ax + b$ を削除する
  • 時間計算量: $O(\log q)$
• void get(T x)
  • $x$ における最小値を取得する
  • 時間計算量: $O(\log q)$
• vector<T> run()
  • クエリを実行し，getの結果を返す
  • 時間計算量: $O(q\log^2 q)$

Reference

• オフライン 削除可能 Convex Hull Trick - procon
• verify: https://codeforces.com/contest/678/submission/131471122

Depends on

• Undoable Li Chao Tree (data-structure/cht/undoable_li_chao_tree.hpp)

Code

#pragma once
#include <bit>
#include <cassert>
#include <map>
#include <utility>
#include <vector>

#include "undoable_li_chao_tree.hpp"

template <typename T>
class OfflineDeletableConvexHullTrick {
   public:
    void insert(T a, T b) { open.insert({{a, b}, now++}); }

    void erase(T a, T b) {
        auto it = open.find({a, b});
        assert(it != open.end());
        closed.emplace_back(a, b, it->second, now++);
        open.erase(it);
    }

    void get(T x) {
        query[now++] = x;
        xs.push_back(x);
    }

    std::vector<T> run() {
        if (xs.empty()) return {};

        // erase lines
        for (auto [line, s] : open) {
            closed.emplace_back(line.first, line.second, s, now);
        }

        // build a segment tree
        int size = std::bit_ceil((unsigned int)now);
        std::vector<std::vector<std::pair<T, T>>> lines(2 * size);

        for (auto [a, b, s, t] : closed) {
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) lines[s++].emplace_back(a, b);
                if (t & 1) lines[--t].emplace_back(a, b);
            }
        }

        // handle queries
        UndoableLiChaoTree<T> lct(xs);
        std::vector<T> ret;

        auto dfs = [&](const auto& dfs, int k) -> void {
            for (auto [a, b] : lines[k]) {
                lct.add(a, b);
            }
            if (k < size) {
                dfs(dfs, 2 * k);
                dfs(dfs, 2 * k + 1);
            } else if (k < size + now) {
                if (query.contains(k - size)) {
                    ret.push_back(lct.get(query[k - size]));
                }
            }
            for (int i = 0; i < (int)lines[k].size(); ++i) {
                lct.undo();
            }
        };

        dfs(dfs, 1);
        return ret;
    }

   private:
    int now = 0;
    std::multimap<std::pair<T, T>, int> open;
    std::vector<std::tuple<T, T, int, int>> closed;
    std::map<int, T> query;
    std::vector<T> xs;
};

#line 2 "data-structure/cht/offline_deletable_convex_hull_trick.hpp"
#include <bit>
#include <cassert>
#include <map>
#include <utility>
#include <vector>

#line 2 "data-structure/cht/undoable_li_chao_tree.hpp"
#include <algorithm>
#line 5 "data-structure/cht/undoable_li_chao_tree.hpp"
#include <limits>
#line 8 "data-structure/cht/undoable_li_chao_tree.hpp"

/**
 * @brief Undoable Li Chao Tree
 */
template <typename T>
class UndoableLiChaoTree {
   public:
    UndoableLiChaoTree() = default;
    explicit UndoableLiChaoTree(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
        size = std::bit_ceil(xs.size());
        node.resize(2 * size, {0, INF});
        while ((int)xs.size() <= size) xs.push_back(xs.back() + 1);
    }

    void add(T a, T b) {
        history.emplace_back(-1, Line(0, 0));
        Line line(a, b);
        int k = 1, l = 0, r = size;
        while (true) {
            int m = std::midpoint(l, r);
            bool left = line(xs[l]) < node[k](xs[l]);
            bool mid = line(xs[m]) < node[k](xs[m]);
            bool right = line(xs[r]) < node[k](xs[r]);

            if (!left && !right) break;
            if (left && right) {
                history.emplace_back(k, node[k]);
                node[k] = line;
                break;
            }
            if (mid) {
                history.emplace_back(k, node[k]);
                std::swap(node[k], line);
            }
            if (r - l == 1) break;
            if (left != mid) {
                k = 2 * k;
                r = m;
            } else {
                k = 2 * k + 1;
                l = m;
            }
        }
    }

    T get(T x) const {
        int k = std::ranges::lower_bound(xs, x) - xs.begin();
        k += size;
        T res = node[k](x);
        while (k >>= 1) res = std::min(res, node[k](x));
        return res;
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [k, line] = history.back();
            history.pop_back();
            if (k == -1) break;
            node[k] = line;
        }
    }

   private:
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        T operator()(T x) const { return a * x + b; }
    };

    static constexpr T INF = std::numeric_limits<T>::max();

    int size;
    std::vector<T> xs;
    std::vector<Line> node;
    std::vector<std::pair<int, Line>> history;
};
#line 9 "data-structure/cht/offline_deletable_convex_hull_trick.hpp"

template <typename T>
class OfflineDeletableConvexHullTrick {
   public:
    void insert(T a, T b) { open.insert({{a, b}, now++}); }

    void erase(T a, T b) {
        auto it = open.find({a, b});
        assert(it != open.end());
        closed.emplace_back(a, b, it->second, now++);
        open.erase(it);
    }

    void get(T x) {
        query[now++] = x;
        xs.push_back(x);
    }

    std::vector<T> run() {
        if (xs.empty()) return {};

        // erase lines
        for (auto [line, s] : open) {
            closed.emplace_back(line.first, line.second, s, now);
        }

        // build a segment tree
        int size = std::bit_ceil((unsigned int)now);
        std::vector<std::vector<std::pair<T, T>>> lines(2 * size);

        for (auto [a, b, s, t] : closed) {
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) lines[s++].emplace_back(a, b);
                if (t & 1) lines[--t].emplace_back(a, b);
            }
        }

        // handle queries
        UndoableLiChaoTree<T> lct(xs);
        std::vector<T> ret;

        auto dfs = [&](const auto& dfs, int k) -> void {
            for (auto [a, b] : lines[k]) {
                lct.add(a, b);
            }
            if (k < size) {
                dfs(dfs, 2 * k);
                dfs(dfs, 2 * k + 1);
            } else if (k < size + now) {
                if (query.contains(k - size)) {
                    ret.push_back(lct.get(query[k - size]));
                }
            }
            for (int i = 0; i < (int)lines[k].size(); ++i) {
                lct.undo();
            }
        };

        dfs(dfs, 1);
        return ret;
    }

   private:
    int now = 0;
    std::multimap<std::pair<T, T>, int> open;
    std::vector<std::tuple<T, T, int, int>> closed;
    std::map<int, T> query;
    std::vector<T> xs;
};

Back to top page