Joeの精進記録

旧:競プロ練習記録

LinkCutTreeを書きました

拾ったLinkCutTreeの使い方がわからないことがたまにあったので自分で一番使いやすいと思うものを書きました。

けんしんのLazySegmentTreeぼくのImplictTreapとまったく同じインターフェースで使えます。

たまに便利なモノイドが追加されるのでそれが一気にセグ木にもTreapにもLCTにも乗るのはうれしすぎますね。

verify済みです。ソースコードはここからコピペしてください。

#394456 No.399 動的な領主 - yukicoder

使い方は以下のとおりです。

// 上のソースコードにある中ですきなタイプのクエリをとってくる
template <class T0, class T1>
struct MinUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};

int main() {
    // ...
    MinUpdateQuery<int, int> lct;
    // 頂点追加やlink/cut, evertなどもいろいろできる。基本的にpublic関数しか触らなくてよくて、expose忘れとかevert忘れとかしにくいかも
    // uvパスにある頂点の値をxに変える
    lct.update(u, v, x);
    // uvパスにある頂点のminを求める
    lct.query(u, v);
    // ...
}

使いやすすぎないか???