遅延伝搬Link/Cut Tree
(lct/link-cut-tree-lazy.hpp)

View this file on GitHub
Last update: 2026-06-08 17:59:24+09:00
Include: #include "lct/link-cut-tree-lazy.hpp"

Depends on

Verified with

verify/verify-yosupo-ds/yosupo-range-add-range-sum-linkcuttree.test.cpp

Code

#pragma once

#include "splay-lazy-reversible.hpp"

//
#include "link-cut-base.hpp"

template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E),
          T (*ts)(T)>
struct LazyLinkCutTree
    : LinkCutBase<LazyReversibleSplayTree<T, E, f, g, h, ts>> {
  using base = LinkCutBase<LazyReversibleSplayTree<T, E, f, g, h, ts>>;
  using Ptr = typename base::Ptr;

  void set_key(Ptr t, const T& key) override {
    this->evert(t);
    t->key = key;
    this->update(t);
  }

  T get_key(Ptr t) override {
    this->evert(t);
    return t->key;
  }

  void apply(Ptr u, Ptr v, const E& e) {
    this->evert(u);
    this->expose(v);
    this->propagate(v, e);
  }
};

/**
 * @brief 遅延伝搬Link/Cut Tree
 */

#line 2 "lct/link-cut-tree-lazy.hpp"

#line 2 "lct/splay-lazy-reversible.hpp"

#line 2 "lct/lazy-reversible-bbst-base.hpp"

template <typename Tree, typename Node, typename T, typename E, T (*f)(T, T),
          T (*g)(T, E), E (*h)(E, E), T (*ts)(T)>
struct LazyReversibleBBST : Tree {
  using Tree::merge;
  using Tree::split;
  using typename Tree::Ptr;

  LazyReversibleBBST() = default;

  void toggle(Ptr t) {
    if (!t) return;
    swap(t->l, t->r);
    t->sum = ts(t->sum);
    t->rev ^= true;
  }

  T fold(Ptr &t, int a, int b) {
    auto x = split(t, a);
    auto y = split(x.second, b - a);
    auto ret = sum(y.first);
    t = merge(x.first, merge(y.first, y.second));
    return ret;
  }

  void reverse(Ptr &t, int a, int b) {
    auto x = split(t, a);
    auto y = split(x.second, b - a);
    toggle(y.first);
    t = merge(x.first, merge(y.first, y.second));
  }

  void apply(Ptr &t, int a, int b, const E &e) {
    auto x = split(t, a);
    auto y = split(x.second, b - a);
    propagate(y.first, e);
    t = merge(x.first, merge(y.first, y.second));
  }

 protected:
  inline T sum(const Ptr t) { return t ? t->sum : T(); }

  Ptr update(Ptr t) override {
    if (!t) return t;
    t->cnt = 1;
    t->sum = t->key;
    if (t->l) t->cnt += t->l->cnt, t->sum = f(t->l->sum, t->sum);
    if (t->r) t->cnt += t->r->cnt, t->sum = f(t->sum, t->r->sum);
    return t;
  }

  void push(Ptr t) override {
    if (!t) return;
    if (t->rev) {
      if (t->l) toggle(t->l);
      if (t->r) toggle(t->r);
      t->rev = false;
    }
    if (t->lazy != E()) {
      if (t->l) propagate(t->l, t->lazy);
      if (t->r) propagate(t->r, t->lazy);
      t->lazy = E();
    }
  }

  void propagate(Ptr t, const E &x) {
    t->lazy = h(t->lazy, x);
    t->key = g(t->key, x);
    t->sum = g(t->sum, x);
  }
};

/**
 * @brief 遅延伝搬反転可能平衡二分木(基底クラス)
 */
#line 2 "lct/splay-base.hpp"

template <typename Node>
struct SplayTreeBase {
  using Ptr = Node *;
  template <typename... Args>
  Ptr my_new(const Args &...args) {
    return new Node(args...);
  }
  void my_del(Ptr p) { delete p; }

  bool is_root(Ptr t) { return !(t->p) || (t->p->l != t && t->p->r != t); }

  int size(Ptr t) const { return count(t); }

  virtual void splay(Ptr t) {
    if (!t) return;
    push(t);
    while (!is_root(t)) {
      Ptr q = t->p;
      if (is_root(q)) {
        push(q), push(t);
        rot(t);
      } else {
        Ptr r = q->p;
        push(r), push(q), push(t);
        if (pos(q) == pos(t))
          rot(q), rot(t);
        else
          rot(t), rot(t);
      }
    }
  }

  Ptr get_left(Ptr t) {
    while (t->l) push(t), t = t->l;
    return t;
  }

  Ptr get_right(Ptr t) {
    while (t->r) push(t), t = t->r;
    return t;
  }

  Ptr kth(Ptr t, int k) {
    while (true) {
      push(t);
      int lsz = count(t->l);
      if (k < lsz) {
        t = t->l;
      } else if (k == lsz) {
        splay(t);
        return t;
      } else {
        k -= lsz + 1;
        t = t->r;
      }
    }
  }

  pair<Ptr, Ptr> split(Ptr t, int k) {
    if (!t) return {nullptr, nullptr};
    if (k == 0) return {nullptr, t};
    if (k == count(t)) return {t, nullptr};

    Ptr r = kth(t, k);
    Ptr l = r->l;
    r->l = nullptr;
    if (l) l->p = nullptr;
    update(r);
    return {l, r};
  }

  Ptr merge(Ptr l, Ptr r) {
    if (!l && !r) return nullptr;
    if (!l) return r;
    if (!r) return l;

    l = kth(l, count(l) - 1);
    l->r = r;
    r->p = l;
    update(l);
    return l;
  }

  using Key = decltype(Node::key);
  Ptr build(const vector<Key> &v) { return build(0, v.size(), v); }
  Ptr build(int l, int r, const vector<Key> &v) {
    if (l == r) return nullptr;
    if (l + 1 == r) return my_new(v[l]);
    return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v));
  }

  template <typename... Args>
  void insert(Ptr &t, int k, const Args &...args) {
    splay(t);
    auto x = split(t, k);
    t = merge(merge(x.first, my_new(args...)), x.second);
  }

  void erase(Ptr &t, int k) {
    splay(t);
    auto x = split(t, k);
    auto y = split(x.second, 1);
    my_del(y.first);
    t = merge(x.first, y.second);
  }

  virtual Ptr update(Ptr t) = 0;

 protected:
  inline int count(Ptr t) const { return t ? t->cnt : 0; }

  virtual void push(Ptr t) = 0;

  Ptr build(const vector<Ptr> &v) { return build(0, v.size(), v); }

  Ptr build(int l, int r, const vector<Ptr> &v) {
    if (l + 1 >= r) return v[l];
    return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v));
  }

  inline int pos(Ptr t) {
    if (t->p) {
      if (t->p->l == t) return -1;
      if (t->p->r == t) return 1;
    }
    return 0;
  }

  virtual void rot(Ptr t) {
    Ptr x = t->p, y = x->p;
    if (pos(t) == -1) {
      if ((x->l = t->r)) t->r->p = x;
      t->r = x, x->p = t;
    } else {
      if ((x->r = t->l)) t->l->p = x;
      t->l = x, x->p = t;
    }
    update(x), update(t);
    if ((t->p = y)) {
      if (y->l == x) y->l = t;
      if (y->r == x) y->r = t;
    }
  }
};

/**
 * @brief Splay Tree(base)
 */
#line 5 "lct/splay-lazy-reversible.hpp"

template <typename T, typename E>
struct LazyReversibleSplayTreeNode {
  using Ptr = LazyReversibleSplayTreeNode *;
  Ptr l, r, p;
  T key, sum;
  E lazy;
  int cnt;
  bool rev;

  LazyReversibleSplayTreeNode(const T &t = T(), const E &e = E())
      : l(), r(), p(), key(t), sum(t), lazy(e), cnt(1), rev(false) {}
};

template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E),
          T (*ts)(T)>
struct LazyReversibleSplayTree
    : LazyReversibleBBST<SplayTreeBase<LazyReversibleSplayTreeNode<T, E>>,
                         LazyReversibleSplayTreeNode<T, E>, T, E, f, g, h, ts> {
  using Node = LazyReversibleSplayTreeNode<T, E>;
};

/**
 * @brief 遅延伝搬反転可能Splay Tree
 */
#line 4 "lct/link-cut-tree-lazy.hpp"

//
#line 2 "lct/link-cut-base.hpp"

template <typename Splay>
struct LinkCutBase : Splay {
  using Node = typename Splay::Node;
  using Ptr = Node*;

  virtual Ptr expose(Ptr t) {
    Ptr rp = nullptr;
    for (Ptr cur = t; cur; cur = cur->p) {
      this->splay(cur);
      cur->r = rp;
      this->update(cur);
      rp = cur;
    }
    this->splay(t);
    return rp;
  }

  virtual void link(Ptr u, Ptr v) {
    evert(u);
    expose(v);
    u->p = v;
  }

  void cut(Ptr u, Ptr v) {
    evert(u);
    expose(v);
    assert(u->p == v);
    v->l = u->p = nullptr;
    this->update(v);
  }

  void evert(Ptr t) {
    expose(t);
    this->toggle(t);
    this->push(t);
  }

  Ptr lca(Ptr u, Ptr v) {
    if (get_root(u) != get_root(v)) return nullptr;
    expose(u);
    return expose(v);
  }

  Ptr get_kth(Ptr x, int k) {
    expose(x);
    while (x) {
      this->push(x);
      if (x->r && x->r->sz > k) {
        x = x->r;
      } else {
        if (x->r) k -= x->r->sz;
        if (k == 0) return x;
        k -= 1;
        x = x->l;
      }
    }
    return nullptr;
  }

  Ptr get_root(Ptr x) {
    expose(x);
    while (x->l) this->push(x), x = x->l;
    return x;
  }

  Ptr get_parent(Ptr x) {
    expose(x);
    Ptr p = x->l;
    if(p == nullptr) return nullptr;
    while (true) {
      this->push(p);
      if (p->r == nullptr) return p;
      p = p->r;
    }
    exit(1);
  }

  virtual void set_key(Ptr t, const decltype(Node::key)& key) {
    this->splay(t);
    t->key = key;
    this->update(t);
  }

  virtual decltype(Node::key) get_key(Ptr t) { return t->key; }

  decltype(Node::key) fold(Ptr u, Ptr v) {
    evert(u);
    expose(v);
    return v->sum;
  }
};

/**
 * @brief Link/Cut Tree(base)
 */
#line 7 "lct/link-cut-tree-lazy.hpp"

template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E),
          T (*ts)(T)>
struct LazyLinkCutTree
    : LinkCutBase<LazyReversibleSplayTree<T, E, f, g, h, ts>> {
  using base = LinkCutBase<LazyReversibleSplayTree<T, E, f, g, h, ts>>;
  using Ptr = typename base::Ptr;

  void set_key(Ptr t, const T& key) override {
    this->evert(t);
    t->key = key;
    this->update(t);
  }

  T get_key(Ptr t) override {
    this->evert(t);
    return t->key;
  }

  void apply(Ptr u, Ptr v, const E& e) {
    this->evert(u);
    this->expose(v);
    this->propagate(v, e);
  }
};

/**
 * @brief 遅延伝搬Link/Cut Tree
 */

Nyaan's Library

This documentation is automatically generated by online-judge-tools/verification-helper

遅延伝搬Link/Cut Tree
(lct/link-cut-tree-lazy.hpp)

Depends on

Verified with

Code

遅延伝搬Link/Cut Tree (lct/link-cut-tree-lazy.hpp)

Depends on

Verified with

Code

遅延伝搬Link/Cut Tree
(lct/link-cut-tree-lazy.hpp)