kazuma8128’s blog

競プロの面白い問題を解きます

Educational Codeforces Round 13 F Lena and Queries

Segment Tree Convex Hull Trick 永続データ構造

問題文

http://codeforces.com/problemset/problem/678/F

問題概要

直線の式の集合 S があります（最初は空集合）. 以下の3種類のクエリを N 個処理せよ

  1. 追加 ： 直線の式 f_i(x) = a * x + b を S に追加
  2. 削除 ： x 回目のクエリで追加した直線の式を削除
  3. 質問 ： max { f_i(q) } (f_i ∈ S) 求めよ

解法

まあつまり, Convex Hull Trick でできるクエリに削除を追加したものをオフラインで求めよってことですね.
Editorial 曰く, クエリ平方分割をすると O(N * sqrt(N)) でできるみたいです. まあ, たしかに….


でもそれだとあんまり面白くないので, これを利用できる解法で解いてみたいと思います.

発想は, 一般グラフでの Dynamic Connectivity *1と同じです.

時系列をセグメントツリーみたいにして, 各直線の式に対して, 追加クエリ~削除クエリの区間に insert するように追加しておきます.
最後にそのセグメントツリーを dfs していって, 潜るときは insert していって, 戻るときは rollback して, 葉で質問クエリに答えます.

Convex Hull Trick はこのやり方ならただのセグメントツリーなので, 永続化が簡単にできます.
永続化できれば rollback する必要はありません.
これで, 計算量 O(N * (logN)^2) になりました.


しかし投げてみると, MLE.（ソースコード）

空間計算量も O(N * (logN)^2) だからですね.

しょうがないので, 空間計算量を減らしましょう.

やることは単純で, LiChao Segment Tree を完全永続化まではせずに, 変更した位置と前の値の履歴をスタックに積んでいって rollback する Union-Find と同じようにやります.

このとき一見, 変更回数が O(N logN) 個なので履歴のスタックにメモリが O(N logN) 必要なように思えますが, よくよく考えると時系列のセグメントツリーで根から葉まで潜っていく間に直線の式が insert される回数は, 高々 N 回であることに気づきます. （なぜなら, 最初に時系列の一区間に insert するとき, 根から各葉までの間に insert される個数は高々一個だからです）

なのでじつは履歴は最大でも O(N) のメモリしか使いません.

これで時間計算量 O(N * (logN)^2), 空間計算量 O(N) になるので通ります.

ソースコード

http://codeforces.com/contest/678/submission/36270642

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

template<typename T>
class retroactive_array {
    vector<T> data;
    vector<pair<int, T>> hist;
public:
    retroactive_array(int N) : data(N) {}
    retroactive_array(int N, T val) : data(N, val) {}
    retroactive_array(const vector<T>& v) : data(v) {}
    retroactive_array(vector<T>&& v) : data(move(v)) {}
    void change(int k, T val) {
        hist.emplace_back(k, data[k]);
        data[k] = val;
    }
    T operator[](int k) const {
        return data[k];
    }
    int getversion() const {
        return hist.size();
    }
    void rollback(int ver) {
        assert(0 <= ver && ver <= (int)hist.size());
        int cnt = hist.size() - ver;
        while (cnt--) {
            data[hist.back().first] = hist.back().second;
            hist.pop_back();
        }
    }
};

template <typename T, const T id>
class retroactive_CHT {
    struct line {
        T a, b;
        line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
        T get(T x) const { return a * x + b; }
    };
    struct node {
        line l;
        node *lch, *rch;
        node(line l_) : l(l_), lch(nullptr), rch(nullptr) {}
    };
    const int n;
    const vector<T> pos;
    retroactive_array<line> data;
    void modify(int p, int lb, int ub, line& l) {
        if (data[p].a == id) {
            data.change(p, l);
            return;
        }
        if (data[p].get(pos[lb]) >= l.get(pos[lb]) && data[p].get(pos[ub - 1]) >= l.get(pos[ub - 1])) return;
        if (data[p].get(pos[lb]) <= l.get(pos[lb]) && data[p].get(pos[ub - 1]) <= l.get(pos[ub - 1])) {
            data.change(p, l);
            return;
        }
        int c = (lb + ub) >> 1;
        if (data[p].get(pos[c]) < l.get(pos[c])) {
            line tmp = data[p];
            data.change(p, l);
            l = tmp;
        }
        if (data[p].get(pos[lb]) <= l.get(pos[lb]))
            modify(p << 1, lb, c, l);
        else
            modify((p << 1) | 1, c, ub, l);
    }
    T sub(int p, int lb, int ub, int t) const {
        if (data[p].a == id) return id;
        if (ub - lb == 1) return data[p].get(pos[t]);
        int c = (lb + ub) >> 1;
        if (t < c) return max(data[p].get(pos[t]), sub(p << 1, lb, c, t));
        return max(data[p].get(pos[t]), sub((p << 1) | 1, c, ub, t));
    }
public:
    retroactive_CHT(const vector<T>& pos_) : n(pos_.size()), pos(pos_), data(n << 2, line(id, id)) {}
    void insert(T a, T b) {
        line l(a, b);
        modify(1, 0, n, l);
    }
    T get(T x) const {
        int t = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
        assert(t < n && pos[t] == x);
        return sub(1, 0, n, t);
    }
    int get_version() const {
        return data.getversion();
    }
    void rollback(int ver) {
        data.rollback(ver);
    }
};

using CHT = retroactive_CHT<ll, LLONG_MIN>;


const int MAX = 1 << 19;

vector<pii> lines[MAX << 1];
int used[MAX];
int que[MAX];

vector<ll> res;

void add_range_line(int l, int r, int a, int b, int p = 1, int lb = 0, int ub = MAX) {
    if (r <= lb || ub <= l) return;
    if (l <= lb && ub <= r) {
        lines[p].emplace_back(a, b);
        return;
    }
    add_range_line(l, r, a, b, p << 1, lb, (lb + ub) >> 1);
    add_range_line(l, r, a, b, (p << 1) | 1, (lb + ub) >> 1, ub);
}

void dfs(int p, CHT& cht) {
    int ver = cht.get_version();
    for (auto l : lines[p]) {
        cht.insert(l.first, l.second);
    }
    if (p >= MAX) {
        if (used[p - MAX]) {
            res.push_back(cht.get(que[p - MAX]));
        }
    }
    else {
        dfs(p << 1, cht);
        dfs((p << 1) | 1, cht);
    }
    cht.rollback(ver);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    vector<int> ex(n);
    vector<ll> pos;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            cin >> a[i] >> b[i];
            ex[i] = 1;
        }
        else if (t == 2) {
            int x;
            cin >> x; x--;
            add_range_line(x, i, a[x], b[x]);
            ex[x] = 0;
        }
        else {
            int x;
            cin >> x;
            pos.push_back(x);
            used[i] = 1;
            que[i] = x;
        }
    }
    for (int i = 0; i < n; i++) {
        if (ex[i]) {
            add_range_line(i, n, a[i], b[i]);
        }
    }
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    if (pos.empty()) {
        return 0;
    }
    CHT cht(pos);
    dfs(1, cht);
    for (auto& ans : res) {
        if (ans == LLONG_MIN) {
            puts("EMPTY SET");
        }
        else {
            printf("%lld\n", ans);
        }
    }
    return 0;
}

僕の Convex Hull Trick は空の pos （クエリの x の候補）を渡して作った後に insert を呼び出すと RE するので注意してください

*1:とてもわかりやすい解説（スライドのP.52~）