拾った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); // ... }
使いやすすぎないか???