implicit_lazy_treap.hpp

SECTIONData Structure INCLUDEnoya/implicit_lazy_treap.hpp

在隐式 Treap 序列上增加区间懒操作和翻转；适合需要剪切、拼接并批量修改子段的动态序列。

Complexity: Time: Expected O(log n) per insertion, erasure, reversal, range update, or range product. Space: O(n) nodes and O(log n) expected recursion stack.

AC 记录：dynamic_sequence_range_affine_range_sum。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: Expected O(log n) per insertion, erasure, reversal,
/// range update, or range product.
/// Space: O(n) nodes and O(log n) expected recursion stack.

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
          auto id>
struct implicit_lazy_treap {
  struct node {
    S val;
    S fwd;
    S bwd;
    F lz;
    std::uint64_t rnd;
    int ls = -1;
    int rs = -1;
    int sz = 1;
    bool rev = false;
  };

  std::vector<node> tr;
  int rt = -1;

  implicit_lazy_treap() = default;
  explicit implicit_lazy_treap(const std::vector<S> &a) {
    tr.reserve(a.size());
    for (const S &val : a) {
      rt = merge(rt, make_node(val));
    }
  }

  int size() const { return node_size(rt); }
  bool empty() const { return rt == -1; }
  void reserve(int cap) { tr.reserve(cap); }

  void insert(int pos, const S &val) {
    assert(0 <= pos && pos <= size());
    auto [l, r] = split(rt, pos);
    rt = merge(merge(l, make_node(val)), r);
  }

  S erase(int pos) {
    assert(0 <= pos && pos < size());
    auto [l, suf] = split(rt, pos);
    auto [mid, r] = split(suf, 1);
    push(mid);
    S res = tr[mid].val;
    rt = merge(l, r);
    return res;
  }

  void reverse(int l, int r) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    apply_reverse(mid);
    rt = merge(pre, merge(mid, tl));
  }

  void apply(int l, int r, const F &tag) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    apply_action(mid, tag);
    rt = merge(pre, merge(mid, tl));
  }

  S prod(int l, int r) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    S res = aggregate(mid, false);
    rt = merge(pre, merge(mid, tl));
    return res;
  }

  std::vector<S> to_vector() {
    std::vector<S> res;
    res.reserve(size());
    auto dfs = [&](auto &f, int cur) -> void {
      if (cur == -1) {
        return;
      }
      push(cur);
      f(f, tr[cur].ls);
      res.push_back(tr[cur].val);
      f(f, tr[cur].rs);
    };
    dfs(dfs, rt);
    return res;
  }

private:
  std::uint64_t rng = 0x243f6a8885a308d3ULL;

  int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
  S aggregate(int cur, bool bwd) const {
    if (cur == -1) {
      return e();
    }
    return bwd ? tr[cur].bwd : tr[cur].fwd;
  }

  std::uint64_t next_priority() {
    std::uint64_t val = (rng += 0x9e3779b97f4a7c15ULL);
    val = (val ^ (val >> 30)) * 0xbf58476d1ce4e5b9ULL;
    val = (val ^ (val >> 27)) * 0x94d049bb133111ebULL;
    return val ^ (val >> 31);
  }

  int make_node(const S &val) {
    tr.push_back({val, val, val, id(), next_priority(), -1, -1, 1, false});
    return int(tr.size()) - 1;
  }

  void apply_reverse(int cur) {
    if (cur == -1) {
      return;
    }
    std::swap(tr[cur].ls, tr[cur].rs);
    std::swap(tr[cur].fwd, tr[cur].bwd);
    tr[cur].rev = !tr[cur].rev;
  }

  void apply_action(int cur, const F &tag) {
    if (cur == -1) {
      return;
    }
    tr[cur].val = mapping(tag, tr[cur].val);
    tr[cur].fwd = mapping(tag, tr[cur].fwd);
    tr[cur].bwd = mapping(tag, tr[cur].bwd);
    tr[cur].lz = composition(tag, tr[cur].lz);
  }

  void push(int cur) {
    if (cur == -1) {
      return;
    }
    if (tr[cur].rev) {
      apply_reverse(tr[cur].ls);
      apply_reverse(tr[cur].rs);
      tr[cur].rev = false;
    }
    apply_action(tr[cur].ls, tr[cur].lz);
    apply_action(tr[cur].rs, tr[cur].lz);
    tr[cur].lz = id();
  }

  void pull(int cur) {
    tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
    tr[cur].fwd = op(op(aggregate(tr[cur].ls, false), tr[cur].val),
                     aggregate(tr[cur].rs, false));
    tr[cur].bwd = op(op(aggregate(tr[cur].rs, true), tr[cur].val),
                     aggregate(tr[cur].ls, true));
  }

  std::pair<int, int> split(int cur, int lsz) {
    if (cur == -1) {
      return {-1, -1};
    }
    push(cur);
    if (node_size(tr[cur].ls) >= lsz) {
      auto [l, r] = split(tr[cur].ls, lsz);
      tr[cur].ls = r;
      pull(cur);
      return {l, cur};
    }
    auto [l, r] = split(tr[cur].rs, lsz - node_size(tr[cur].ls) - 1);
    tr[cur].rs = l;
    pull(cur);
    return {cur, r};
  }

  int merge(int l, int r) {
    if (l == -1 || r == -1) {
      return l == -1 ? r : l;
    }
    if (tr[l].rnd > tr[r].rnd) {
      push(l);
      tr[l].rs = merge(tr[l].rs, r);
      pull(l);
      return l;
    }
    push(r);
    tr[r].ls = merge(l, tr[r].ls);
    pull(r);
    return r;
  }

  void check_range(int l, int r) const {
    assert(0 <= l && l <= r && r <= size());
  }
};

} // namespace noya

#ifndef NOYA_IMPLICIT_LAZY_TREAP_HPP
#define NOYA_IMPLICIT_LAZY_TREAP_HPP 1

/// @complexity Time: Expected O(log n) per insertion, erasure, reversal,
/// range update, or range product.
/// Space: O(n) nodes and O(log n) expected recursion stack.

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
          auto id>
struct implicit_lazy_treap {
  struct node {
    S val;
    S fwd;
    S bwd;
    F lz;
    std::uint64_t rnd;
    int ls = -1;
    int rs = -1;
    int sz = 1;
    bool rev = false;
  };

  std::vector<node> tr;
  int rt = -1;

  implicit_lazy_treap() = default;
  explicit implicit_lazy_treap(const std::vector<S> &a) {
    tr.reserve(a.size());
    for (const S &val : a) {
      rt = merge(rt, make_node(val));
    }
  }

  int size() const { return node_size(rt); }
  bool empty() const { return rt == -1; }
  void reserve(int cap) { tr.reserve(cap); }

  void insert(int pos, const S &val) {
    assert(0 <= pos && pos <= size());
    auto [l, r] = split(rt, pos);
    rt = merge(merge(l, make_node(val)), r);
  }

  S erase(int pos) {
    assert(0 <= pos && pos < size());
    auto [l, suf] = split(rt, pos);
    auto [mid, r] = split(suf, 1);
    push(mid);
    S res = tr[mid].val;
    rt = merge(l, r);
    return res;
  }

  void reverse(int l, int r) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    apply_reverse(mid);
    rt = merge(pre, merge(mid, tl));
  }

  void apply(int l, int r, const F &tag) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    apply_action(mid, tag);
    rt = merge(pre, merge(mid, tl));
  }

  S prod(int l, int r) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    S res = aggregate(mid, false);
    rt = merge(pre, merge(mid, tl));
    return res;
  }

  std::vector<S> to_vector() {
    std::vector<S> res;
    res.reserve(size());
    auto dfs = [&](auto &f, int cur) -> void {
      if (cur == -1) {
        return;
      }
      push(cur);
      f(f, tr[cur].ls);
      res.push_back(tr[cur].val);
      f(f, tr[cur].rs);
    };
    dfs(dfs, rt);
    return res;
  }

private:
  std::uint64_t rng = 0x243f6a8885a308d3ULL;

  int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
  S aggregate(int cur, bool bwd) const {
    if (cur == -1) {
      return e();
    }
    return bwd ? tr[cur].bwd : tr[cur].fwd;
  }

  std::uint64_t next_priority() {
    std::uint64_t val = (rng += 0x9e3779b97f4a7c15ULL);
    val = (val ^ (val >> 30)) * 0xbf58476d1ce4e5b9ULL;
    val = (val ^ (val >> 27)) * 0x94d049bb133111ebULL;
    return val ^ (val >> 31);
  }

  int make_node(const S &val) {
    tr.push_back({val, val, val, id(), next_priority(), -1, -1, 1, false});
    return int(tr.size()) - 1;
  }

  void apply_reverse(int cur) {
    if (cur == -1) {
      return;
    }
    std::swap(tr[cur].ls, tr[cur].rs);
    std::swap(tr[cur].fwd, tr[cur].bwd);
    tr[cur].rev = !tr[cur].rev;
  }

  void apply_action(int cur, const F &tag) {
    if (cur == -1) {
      return;
    }
    tr[cur].val = mapping(tag, tr[cur].val);
    tr[cur].fwd = mapping(tag, tr[cur].fwd);
    tr[cur].bwd = mapping(tag, tr[cur].bwd);
    tr[cur].lz = composition(tag, tr[cur].lz);
  }

  void push(int cur) {
    if (cur == -1) {
      return;
    }
    if (tr[cur].rev) {
      apply_reverse(tr[cur].ls);
      apply_reverse(tr[cur].rs);
      tr[cur].rev = false;
    }
    apply_action(tr[cur].ls, tr[cur].lz);
    apply_action(tr[cur].rs, tr[cur].lz);
    tr[cur].lz = id();
  }

  void pull(int cur) {
    tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
    tr[cur].fwd = op(op(aggregate(tr[cur].ls, false), tr[cur].val),
                     aggregate(tr[cur].rs, false));
    tr[cur].bwd = op(op(aggregate(tr[cur].rs, true), tr[cur].val),
                     aggregate(tr[cur].ls, true));
  }

  std::pair<int, int> split(int cur, int lsz) {
    if (cur == -1) {
      return {-1, -1};
    }
    push(cur);
    if (node_size(tr[cur].ls) >= lsz) {
      auto [l, r] = split(tr[cur].ls, lsz);
      tr[cur].ls = r;
      pull(cur);
      return {l, cur};
    }
    auto [l, r] = split(tr[cur].rs, lsz - node_size(tr[cur].ls) - 1);
    tr[cur].rs = l;
    pull(cur);
    return {cur, r};
  }

  int merge(int l, int r) {
    if (l == -1 || r == -1) {
      return l == -1 ? r : l;
    }
    if (tr[l].rnd > tr[r].rnd) {
      push(l);
      tr[l].rs = merge(tr[l].rs, r);
      pull(l);
      return l;
    }
    push(r);
    tr[r].ls = merge(l, tr[r].ls);
    pull(r);
    return r;
  }

  void check_range(int l, int r) const {
    assert(0 <= l && l <= r && r <= size());
  }
};

} // namespace noya

#endif // NOYA_IMPLICIT_LAZY_TREAP_HPP

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

/// @complexity Time: Expected O(log n) per insertion, erasure, reversal,
/// range update, or range product.
/// Space: O(n) nodes and O(log n) expected recursion stack.

namespace noya {

/// @brief Implicit randomized treap with reversible monoid products and lazy
/// range actions. Each node stores both product orders, so reversing a range
/// only swaps its children and its forward/backward aggregates. A pending
/// action is composed at a subtree root and pushed only before structural
/// changes, which keeps every sequence operation logarithmic in expectation.
template <class S, class F, auto op, auto e, auto mapping, auto composition,
          auto id>
struct implicit_lazy_treap {
  struct node {
    S val;
    S fwd;
    S bwd;
    F lz;
    std::uint64_t rnd;
    int ls = -1;
    int rs = -1;
    int sz = 1;
    bool rev = false;
  };

  std::vector<node> tr;
  int rt = -1;

  implicit_lazy_treap() = default;
  explicit implicit_lazy_treap(const std::vector<S> &a) {
    tr.reserve(a.size());
    for (const S &val : a) {
      rt = merge(rt, make_node(val));
    }
  }

  int size() const { return node_size(rt); }
  bool empty() const { return rt == -1; }
  void reserve(int cap) { tr.reserve(cap); }

  void insert(int pos, const S &val) {
    assert(0 <= pos && pos <= size());
    auto [l, r] = split(rt, pos);
    rt = merge(merge(l, make_node(val)), r);
  }

  S erase(int pos) {
    assert(0 <= pos && pos < size());
    auto [l, suf] = split(rt, pos);
    auto [mid, r] = split(suf, 1);
    push(mid);
    S res = tr[mid].val;
    rt = merge(l, r);
    return res;
  }

  void reverse(int l, int r) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    apply_reverse(mid);
    rt = merge(pre, merge(mid, tl));
  }

  void apply(int l, int r, const F &tag) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    apply_action(mid, tag);
    rt = merge(pre, merge(mid, tl));
  }

  S prod(int l, int r) {
    check_range(l, r);
    auto [pre, suf] = split(rt, l);
    auto [mid, tl] = split(suf, r - l);
    S res = aggregate(mid, false);
    rt = merge(pre, merge(mid, tl));
    return res;
  }

  std::vector<S> to_vector() {
    std::vector<S> res;
    res.reserve(size());
    auto dfs = [&](auto &f, int cur) -> void {
      if (cur == -1) {
        return;
      }
      push(cur);
      f(f, tr[cur].ls);
      res.push_back(tr[cur].val);
      f(f, tr[cur].rs);
    };
    dfs(dfs, rt);
    return res;
  }

private:
  std::uint64_t rng = 0x243f6a8885a308d3ULL;

  int node_size(int cur) const { return cur == -1 ? 0 : tr[cur].sz; }
  S aggregate(int cur, bool bwd) const {
    if (cur == -1) {
      return e();
    }
    return bwd ? tr[cur].bwd : tr[cur].fwd;
  }

  std::uint64_t next_priority() {
    std::uint64_t val = (rng += 0x9e3779b97f4a7c15ULL);
    val = (val ^ (val >> 30)) * 0xbf58476d1ce4e5b9ULL;
    val = (val ^ (val >> 27)) * 0x94d049bb133111ebULL;
    return val ^ (val >> 31);
  }

  int make_node(const S &val) {
    tr.push_back({val, val, val, id(), next_priority(), -1, -1, 1, false});
    return int(tr.size()) - 1;
  }

  void apply_reverse(int cur) {
    if (cur == -1) {
      return;
    }
    std::swap(tr[cur].ls, tr[cur].rs);
    std::swap(tr[cur].fwd, tr[cur].bwd);
    tr[cur].rev = !tr[cur].rev;
  }

  void apply_action(int cur, const F &tag) {
    if (cur == -1) {
      return;
    }
    tr[cur].val = mapping(tag, tr[cur].val);
    tr[cur].fwd = mapping(tag, tr[cur].fwd);
    tr[cur].bwd = mapping(tag, tr[cur].bwd);
    tr[cur].lz = composition(tag, tr[cur].lz);
  }

  void push(int cur) {
    if (cur == -1) {
      return;
    }
    if (tr[cur].rev) {
      apply_reverse(tr[cur].ls);
      apply_reverse(tr[cur].rs);
      tr[cur].rev = false;
    }
    apply_action(tr[cur].ls, tr[cur].lz);
    apply_action(tr[cur].rs, tr[cur].lz);
    tr[cur].lz = id();
  }

  void pull(int cur) {
    tr[cur].sz = 1 + node_size(tr[cur].ls) + node_size(tr[cur].rs);
    tr[cur].fwd = op(op(aggregate(tr[cur].ls, false), tr[cur].val),
                     aggregate(tr[cur].rs, false));
    tr[cur].bwd = op(op(aggregate(tr[cur].rs, true), tr[cur].val),
                     aggregate(tr[cur].ls, true));
  }

  std::pair<int, int> split(int cur, int lsz) {
    if (cur == -1) {
      return {-1, -1};
    }
    push(cur);
    if (node_size(tr[cur].ls) >= lsz) {
      auto [l, r] = split(tr[cur].ls, lsz);
      tr[cur].ls = r;
      pull(cur);
      return {l, cur};
    }
    auto [l, r] = split(tr[cur].rs, lsz - node_size(tr[cur].ls) - 1);
    tr[cur].rs = l;
    pull(cur);
    return {cur, r};
  }

  int merge(int l, int r) {
    if (l == -1 || r == -1) {
      return l == -1 ? r : l;
    }
    if (tr[l].rnd > tr[r].rnd) {
      push(l);
      tr[l].rs = merge(tr[l].rs, r);
      pull(l);
      return l;
    }
    push(r);
    tr[r].ls = merge(l, tr[r].ls);
    pull(r);
    return r;
  }

  void check_range(int l, int r) const {
    assert(0 <= l && l <= r && r <= size());
  }
};

} // namespace noya