library

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

View the Project on GitHub maspypy/library

:warning: ds/piecewise_constant/piecewise_constant_basic.hpp

Depends on

Code

#include "ds/piecewise_constant/piecewise_constant.hpp"

namespace SplayTreeNodes {
template <typename Y>
struct Node_Piecewise_Constant_Basic {
  struct S {
    ll x1, x2;  // y on [x1,x2)
    Y y;
    Border_Type c1, c2;
  };
  using value_type = S;
  using operator_type = int;
  using Y_type = Y;
  using np = Node_Piecewise_Constant_Basic*;

  np p, l, r;
  bool rev;
  S x;
  u32 size;
  ll& x1() { return x.x1; }
  ll& x2() { return x.x2; }
  Border_Type& c1() { return x.c1; }
  Border_Type& c2() { return x.c2; }
  Y& y() { return x.y; }

  int lsize() { return (l ? l->size : 0); }
  int rsize() { return (r ? r->size : 0); }

  static void new_node(np n, const S& x) {
    n->p = n->l = n->r = nullptr;
    n->x = x, n->size = 1, n->rev = 0;
  }

  void update() { size = 1 + lsize() + rsize(); }

  void push() {
    if (rev) {
      if (l) {
        l->rev ^= 1, swap(l->l, l->r);
      }
      if (r) {
        r->rev ^= 1, swap(r->l, r->r);
      }
      rev = 0;
    }
  }

  // update, push 以外で呼ばれるものは、splay 後であることが想定されている。
  // したがってその時点で update, push 済であることを仮定してよい。
  S get() { return x; }
  void set(const S& xx) {
    x = xx;
    update();
  }
  void reverse() {
    swap(l, r);
    rev ^= 1;
  }
};
template <typename Y>
using Piecewise_Constant_Basic =
    Piecewise_Constant<Node_Piecewise_Constant_Basic<Y>>;
}  // namespace SplayTreeNodes

using SplayTreeNodes::Piecewise_Constant_Basic;
#line 1 "ds/node_pool.hpp"
template <class Node>
struct Node_Pool {
  struct Slot {
    union alignas(Node) {
      Slot* next;
      unsigned char storage[sizeof(Node)];
    };
  };
  using np = Node*;

  static constexpr int CHUNK_SIZE = 1 << 16;

  vc<unique_ptr<Slot[]>> chunks;
  Slot* cur = nullptr;
  int cur_used = 0;
  Slot* free_head = nullptr;

  Node_Pool() { alloc_chunk(); }

  template <class... Args>
  np create(Args&&... args) {
    Slot* s = new_slot();
    return ::new (s) Node(forward<Args>(args)...);
  }

  np clone(const np x) {
    assert(x);
    Slot* s = new_slot();
    return ::new (s) Node(*x);  // コピーコンストラクタ呼び出し
  }

  void destroy(np x) {
    if (!x) return;
    x->~Node();
    auto s = reinterpret_cast<Slot*>(x);
    s->next = free_head;
    free_head = s;
  }

  void reset() {
    free_head = nullptr;
    if (!chunks.empty()) {
      cur = chunks[0].get();
      cur_used = 0;
    }
  }

 private:
  void alloc_chunk() {
    chunks.emplace_back(make_unique<Slot[]>(CHUNK_SIZE));
    cur = chunks.back().get();
    cur_used = 0;
  }

  Slot* new_slot() {
    if (free_head) {
      Slot* s = free_head;
      free_head = free_head->next;
      return s;
    }
    if (cur_used == CHUNK_SIZE) alloc_chunk();
    return &cur[cur_used++];
  }
};
#line 3 "ds/splaytree/splaytree.hpp"

// Node 型を別に定義して使う
template <typename Node>
struct SplayTree {
  Node_Pool<Node> pool;
  using np = Node *;
  using X = typename Node::value_type;
  using A = typename Node::operator_type;

  void free_subtree(np c) {
    if (!c) return;
    auto dfs = [&](auto &dfs, np c) -> void {
      if (c->l) dfs(dfs, c->l);
      if (c->r) dfs(dfs, c->r);
      c->p = c->l = c->r = nullptr;
      pool.destroy(c);
    };
    dfs(dfs, c);
  }

  void reset() { pool.reset(); }

  np new_root() { return nullptr; }

  np new_node(const X &x) {
    np n = pool.create();
    Node::new_node(n, x);
    return n;
  }

  np new_node(const vc<X> &dat) {
    auto dfs = [&](auto &dfs, int l, int r) -> np {
      if (l == r) return nullptr;
      if (r == l + 1) return new_node(dat[l]);
      int m = (l + r) / 2;
      np l_root = dfs(dfs, l, m);
      np r_root = dfs(dfs, m + 1, r);
      np root = new_node(dat[m]);
      root->l = l_root, root->r = r_root;
      if (l_root) l_root->p = root;
      if (r_root) r_root->p = root;
      root->update();
      return root;
    };
    return dfs(dfs, 0, len(dat));
  }

  u32 get_size(np root) { return (root ? root->size : 0); }

  np merge(np l_root, np r_root) {
    if (!l_root) return r_root;
    if (!r_root) return l_root;
    assert((!l_root->p) && (!r_root->p));
    splay_kth(r_root, 0);  // splay したので push 済
    r_root->l = l_root;
    l_root->p = r_root;
    r_root->update();
    return r_root;
  }
  np merge3(np a, np b, np c) { return merge(merge(a, b), c); }
  np merge4(np a, np b, np c, np d) { return merge(merge(merge(a, b), c), d); }

  pair<np, np> split(np root, u32 k) {
    assert(!root || !root->p);
    if (k == 0) return {nullptr, root};
    if (k == (root->size)) return {root, nullptr};
    splay_kth(root, k - 1);
    np right = root->r;
    root->r = nullptr, right->p = nullptr;
    root->update();
    return {root, right};
  }
  tuple<np, np, np> split3(np root, u32 l, u32 r) {
    np nm, nr;
    tie(root, nr) = split(root, r);
    tie(root, nm) = split(root, l);
    return {root, nm, nr};
  }
  tuple<np, np, np, np> split4(np root, u32 i, u32 j, u32 k) {
    np d;
    tie(root, d) = split(root, k);
    auto [a, b, c] = split3(root, i, j);
    return {a, b, c, d};
  }

  tuple<np, np, np> split_L_root_R(np root) {
    u32 s = (root->l ? root->l->size : 0);
    return split3(root, s, s + 1);
  }

  // 部分木が区間 [l,r) に対応するようなノードを作って返す
  // そのノードが root になるわけではないので、
  // このノードを参照した後にすぐに splay して根に持ち上げること
  void goto_between(np &root, u32 l, u32 r) {
    if (l == 0 && r == root->size) return;
    if (l == 0) {
      splay_kth(root, r);
      root = root->l;
      return;
    }
    if (r == root->size) {
      splay_kth(root, l - 1);
      root = root->r;
      return;
    }
    splay_kth(root, r);
    np rp = root;
    root = rp->l;
    root->p = nullptr;
    splay_kth(root, l - 1);
    root->p = rp;
    rp->l = root;
    rp->update();
    root = root->r;
  }

  vc<X> get_all(const np &root) {
    vc<X> res;
    auto dfs = [&](auto &dfs, np root) -> void {
      if (!root) return;
      root->push();
      dfs(dfs, root->l);
      res.eb(root->get());
      dfs(dfs, root->r);
    };
    dfs(dfs, root);
    return res;
  }

  X get(np &root, u32 k) {
    assert(root == nullptr || !root->p);
    splay_kth(root, k);
    return root->get();
  }

  void set(np &root, u32 k, const X &x) {
    assert(root != nullptr && !root->p);
    splay_kth(root, k);
    root->set(x);
  }

  void multiply(np &root, u32 k, const X &x) {
    assert(root != nullptr && !root->p);
    splay_kth(root, k);
    root->multiply(x);
  }

  X prod(np &root, u32 l, u32 r) {
    assert(root == nullptr || !root->p);
    using Mono = typename Node::Monoid_X;
    if (l == r) return Mono::unit();
    assert(0 <= l && l < r && r <= root->size);
    goto_between(root, l, r);
    X res = root->prod;
    splay(root, true);
    return res;
  }

  X prod(np &root) {
    assert(root == nullptr || !root->p);
    using Mono = typename Node::Monoid_X;
    return (root ? root->prod : Mono::unit());
  }

  void apply(np &root, u32 l, u32 r, const A &a) {
    if (l == r) return;
    assert(0 <= l && l < r && r <= root->size);
    goto_between(root, l, r);
    root->apply(a);
    splay(root, true);
  }
  void apply(np &root, const A &a) {
    if (!root) return;
    root->apply(a);
  }

  void reverse(np &root, u32 l, u32 r) {
    assert(root == nullptr || !root->p);
    if (l == r) return;
    assert(0 <= l && l < r && r <= root->size);
    goto_between(root, l, r);
    root->reverse();
    splay(root, true);
  }
  void reverse(np root) {
    if (!root) return;
    root->reverse();
  }

  void rotate(Node *n) {
    // n を根に近づける。push, update は rotate の外で行う。
    Node *pp, *p, *c;
    p = n->p;
    pp = p->p;
    if (p->l == n) {
      c = n->r;
      n->r = p;
      p->l = c;
    } else {
      c = n->l;
      n->l = p;
      p->r = c;
    }
    if (pp && pp->l == p) pp->l = n;
    if (pp && pp->r == p) pp->r = n;
    n->p = pp;
    p->p = n;
    if (c) c->p = p;
  }

  void push_from_root(np c) {
    if (!c->p) {
      c->push();
      return;
    }
    push_from_root(c->p);
    c->push();
  }

  void splay(Node *me, bool push_from_root_done) {
    // これを呼ぶ時点で、me の祖先（me を除く）は既に push 済であることを仮定
    // 特に、splay 終了時点で me は upd / push 済である
    if (!push_from_root_done) push_from_root(me);
    me->push();
    while (me->p) {
      np p = me->p;
      np pp = p->p;
      if (!pp) {
        rotate(me);
        p->update();
        break;
      }
      bool same = (p->l == me && pp->l == p) || (p->r == me && pp->r == p);
      if (same) rotate(p), rotate(me);
      if (!same) rotate(me), rotate(me);
      pp->update(), p->update();
    }
    // me の update は最後だけでよい
    me->update();
  }

  void splay_kth(np &root, u32 k) {
    assert(0 <= k && k < (root->size));
    while (1) {
      root->push();
      u32 s1 = (root->l ? root->l->size : 0);
      u32 s2 = (root->size) - (root->r ? root->r->size : 0);
      if (k < s1) root = root->l;
      elif (k < s2) { break; }
      else {
        k -= s2;
        root = root->r;
      }
    }
    splay(root, true);
  }

  // check(x), 左側のノード全体が check を満たすように切る
  template <typename F>
  pair<np, np> split_max_right(np root, F check) {
    if (!root) return {nullptr, nullptr};
    assert(!root->p);
    np c = find_max_right(root, check);
    if (!c) {
      splay(root, true);
      return {nullptr, root};
    }
    splay(c, true);
    np right = c->r;
    if (!right) return {c, nullptr};
    right->p = nullptr;
    c->r = nullptr;
    c->update();
    return {c, right};
  }

  // check(x, cnt), 左側のノード全体が check を満たすように切る
  template <typename F>
  pair<np, np> split_max_right_cnt(np root, F check) {
    if (!root) return {nullptr, nullptr};
    assert(!root->p);
    np c = find_max_right_cnt(root, check);
    if (!c) {
      splay(root, true);
      return {nullptr, root};
    }
    splay(c, true);
    np right = c->r;
    if (!right) return {c, nullptr};
    right->p = nullptr;
    c->r = nullptr;
    c->update();
    return {c, right};
  }

  // 左側のノード全体の prod が check を満たすように切る
  template <typename F>
  pair<np, np> split_max_right_prod(np root, F check) {
    if (!root) return {nullptr, nullptr};
    assert(!root->p);
    np c = find_max_right_prod(root, check);
    if (!c) {
      splay(root, true);
      return {nullptr, root};
    }
    splay(c, true);
    np right = c->r;
    if (!right) return {c, nullptr};
    right->p = nullptr;
    c->r = nullptr;
    c->update();
    return {c, right};
  }

  template <typename F>
  np find_max_right(np root, const F &check) {
    // 最後に見つけた ok の点、最後に探索した点
    np last_ok = nullptr, last = nullptr;
    while (root) {
      last = root;
      root->push();
      if (check(root->x)) {
        last_ok = root;
        root = root->r;
      } else {
        root = root->l;
      }
    }
    splay(last, true);
    return last_ok;
  }

  template <typename F>
  np find_max_right_cnt(np root, const F &check) {
    // 最後に見つけた ok の点、最後に探索した点
    np last_ok = nullptr, last = nullptr;
    ll n = 0;
    while (root) {
      last = root;
      root->push();
      ll k = (root->size) - (root->r ? root->r->size : 0);
      if (check(root->x, n + k)) {
        last_ok = root;
        n += k;
        root = root->r;
      } else {
        root = root->l;
      }
    }
    splay(last, true);
    return last_ok;
  }

  template <typename F>
  np find_max_right_prod(np root, const F &check) {
    using Mono = typename Node::Monoid_X;
    X prod = Mono::unit();
    // 最後に見つけた ok の点、最後に探索した点
    np last_ok = nullptr, last = nullptr;
    while (root) {
      last = root;
      root->push();
      np tmp = root->r;
      root->r = nullptr;
      root->update();
      X lprod = Mono::op(prod, root->prod);
      root->r = tmp;
      root->update();
      if (check(lprod)) {
        prod = lprod;
        last_ok = root;
        root = root->r;
      } else {
        root = root->l;
      }
    }
    splay(last, true);
    return last_ok;
  }
};
#line 2 "ds/piecewise_constant/piecewise_constant.hpp"

enum Border_Type { inc, dec, l, r };

// https://atcoder.jp/contests/cf16-tournament-round3-open/tasks/asaporo_b
// https://atcoder.jp/contests/arc174/tasks/arc174_f
template <typename Node>
struct Piecewise_Constant {
  using Y = typename Node::Y_type;
  SplayTree<Node>& ST;
  using np = Node*;
  using S = typename Node::value_type;
  using App = typename Node::operator_type;
  using BT = Border_Type;
  np root;
  using QUE = pq_min<pair<ll, np>>;
  QUE que_lo, que_hi;
  array<ll, 4> add;
  array<ll, 2> domain;

  vc<np> my_pool;
  np new_node(S x) {
    np c = ST.new_node(x);
    my_pool.eb(c);
    return c;
  }
  ~Piecewise_Constant() {
    for (auto c : my_pool) {
      ST.pool.destroy(c);
    }
  }

  void swap(Piecewise_Constant& other) noexcept {
    ::swap(root, other.root);
    ::swap(que_lo, other.que_lo);
    ::swap(que_hi, other.que_hi);
    ::swap(add, other.add);
    ::swap(domain, other.domain);
    ::swap(my_pool, other.my_pool);
  }

  int size() { return len(my_pool); }

  // f(i) = (x1,x2,y)
  template <typename F>
  Piecewise_Constant(SplayTree<Node>& ST, int n, F f)
      : ST(ST), root(nullptr), add{}, domain{} {
    assert(n > 0);
    vc<S> dat;
    FOR(i, n) {
      auto [x1, x2, y] = f(i);
      if (i == 0) {
        dat.eb(S{x1, x2, y, BT::l, BT::r});
        continue;
      }
      assert(dat.back().x2 == x1);
      if (dat.back().y == y) {
        dat.back().x2 = x2;
        continue;
      }
      BT c = (dat.back().y < y ? BT::inc : BT::dec);
      dat.back().c2 = c;
      dat.eb(S{x1, x2, y, c, BT::r});
    }
    root = nullptr;
    FOR(i, len(dat)) {
      np c = new_node(dat[i]);
      add_que(c);
      root = ST.merge(root, c);
    }
    domain[0] = dat[0].x1, domain[1] = dat.back().x2;
  }

  void shift(ll a) {
    add[0] += a, add[1] += a, add[2] += a, add[3] += a;
    if (domain[0] != -infty<ll>) domain[0] += a;
    if (domain[1] != infty<ll>) domain[1] += a;
  }

  // f(x) を g(x) に変更. g(x)=min_{x+a<=t<=x+b} f(x).
  void slide_min(ll a, ll b) { slide(BT::inc, BT::dec, a, b, que_hi); }

  // f(x) を g(x) に変更. g(x)=max_{x+a<=t<=x+b} f(x).
  void slide_max(ll a, ll b) { slide(BT::dec, BT::inc, a, b, que_lo); }

  vc<tuple<ll, ll, Y>> get_all() {
    vc<tuple<ll, ll, Y>> ANS;
    auto dfs = [&](auto& dfs, np c) -> void {
      auto [x1, x2] = position(c);
      c->push();
      if (c->l) dfs(dfs, c->l);
      ANS.eb(x1, x2, c->y());
      if (c->r) dfs(dfs, c->r);
    };
    dfs(dfs, root);
    return ANS;
  }

  // 定義域の左端が x になるように拡張, y で埋める
  void extend_domain_left(ll x, Y y) {
    if (x == domain[0]) return;
    assert(x < domain[0]);
    ST.splay_kth(root, 0);
    BT color = (y < root->y() ? BT::inc : BT::dec);
    np c = new_node(S{x - add[BT::l], domain[0] - add[color], y, BT::l, color});
    root->c1() = color, root->x1() = domain[0] - add[color];
    add_que(root);
    root = ST.merge(c, root);
    domain[0] = x;
  }

  void apply(ll L, ll R, App app) {
    if (L == R) return;
    auto [A, tmp] = split(root, L, domain[0], domain[1]);
    auto [B, C] = split(tmp, R, L, domain[1]);
    ST.apply(B, app);
    if (A) {
      ST.splay_kth(A, A->size - 1);
      ST.splay_kth(B, 0);
      assert(position(A).se == L && position(B).fi == L);
      BT color = (A->y() < B->y() ? BT::inc : BT::dec);
      A->c2() = color, A->x2() = L - add[color];
      B->c1() = color, B->x1() = L - add[color];
      add_que(A), add_que(B);
    } else {
      ST.splay_kth(B, 0);
      assert(position(B).fi == L);
      B->c1() = BT::l, B->x1() = L - add[BT::l];
    }
    if (C) {
      ST.splay_kth(B, B->size - 1);
      ST.splay_kth(C, 0);
      assert(position(B).se == R && position(C).fi == R);
      BT color = (B->y() < C->y() ? BT::inc : BT::dec);
      B->c2() = color, B->x2() = R - add[color];
      C->c1() = color, C->x1() = R - add[color];
      add_que(B), add_que(C);
    } else {
      ST.splay_kth(B, B->size - 1);
      assert(position(B).se == R);
      B->c2() = BT::r, B->x2() = R - add[BT::r];
    }
    root = ST.merge3(A, B, C);
  }

  Y get(ll x) {
    assert(domain[0] <= x && x < domain[1]);
    root = ST.find_max_right(
        root, [&](S s) -> bool { return (s.x1 + add[s.c1] <= x); });
    ST.splay(root, true);
    return root->y();
  }

  pair<np, np> split(np c, ll x, ll a, ll b) {
    // c の定義域が [a,b)
    assert(a <= x && x <= b);
    if (a == x) return {nullptr, c};
    if (b == x) return {c, nullptr};
    c = ST.find_max_right(c,
                          [&](S s) -> bool { return (s.x1 + add[s.c1] <= x); });
    ST.splay(c, true);
    auto [x1, x2] = position(c);
    if (x1 == x) {
      np l = c->l;
      if (l) l->p = nullptr, c->l = nullptr;
      c->update();
      return {l, c};
    }
    assert(x1 < x && x < x2);
    np cr = new_node(S{x - add[BT::l], c->x2(), c->y(), BT::l, c->c2()});
    c->c2() = BT::r, c->x2() = x - add[BT::r];
    np r = c->r;
    if (!r) {
      c->update(), cr->update();
      return {c, cr};
    }
    c->r = nullptr, cr->r = r, r->p = cr;
    c->update(), cr->update();
    return {c, cr};
  }

 private:
  inline bool active(np c) { return (c->p != nullptr || c == root); }

  pi position(np c) {
    ll x1 = c->x1(), x2 = c->x2();
    if (x1 != -infty<ll>) x1 += add[c->c1()];
    if (x2 != infty<ll>) x2 += add[c->c2()];
    return {x1, x2};
  }

  void slide(BT stay, BT move, ll a, ll b, QUE& que) {
    assert(domain[0] < domain[1]);
    shift(-a);
    b -= a;
    if (domain[1] != infty<ll>) domain[1] -= b;
    while (1) {
      while (len(que)) {
        auto [pri, c] = que.top();
        if (pri + add[move] - add[stay] > b) {
          break;
        }
        elif (!active(c)) { que.pop(); }
        elif (c->c1() != stay || c->c2() != move) { que.pop(); }
        elif (c->x2() - c->x1() != pri) { que.pop(); }
        else {
          auto [x1, x2] = position(c);
          assert(x2 - x1 <= b);
          que.pop();
          ST.splay(c, false);
          // c is deleted
          auto [A, mid, B] = ST.split3(c, c->lsize(), c->lsize() + 1);
          assert(mid == c);

          ST.splay_kth(A, A->size - 1), ST.splay_kth(B, 0);
          BT color = (A->y() < B->y() ? BT::inc : BT::dec);
          if (color == stay) {
            B->c1() = stay, B->x1() = x1 - add[stay];
            add_que(B);
          } else {
            A->c2() = move, A->x2() = x2 - add[move];
            add_que(A);
          }
          root = ST.merge(A, B);
        }
      }
      ST.splay_kth(root, 0);
      auto [x1, x2] = position(root);
      if (x2 - x1 <= b && root->c2() == move) {
        auto [left, B] = ST.split(root, 1);
        ST.splay_kth(B, 0);
        assert(left == root);
        B->c1() = BT::l, B->x1() = x1 - add[BT::l];
        root = B;
        continue;
      }
      ST.splay_kth(root, root->size - 1);
      tie(x1, x2) = position(root);
      if (x2 - x1 <= b && root->c1() == stay) {
        auto [A, right] = ST.split(root, root->size - 1);
        ST.splay_kth(A, A->size - 1);
        assert(right == root);
        A->c2() = BT::r, A->x2() = x2 - add[BT::r];
        root = A;
        continue;
      }
      break;
    }
    add[move] -= b, add[BT::r] -= b;
  }

  void add_que(np c) {
    ll d = c->x2() - c->x1();
    if (c->c1() == BT::inc && c->c2() == BT::dec) {
      que_hi.emplace(d, c);
    }
    if (c->c1() == BT::dec && c->c2() == BT::inc) {
      que_lo.emplace(d, c);
    }
  }
};
#line 2 "ds/piecewise_constant/piecewise_constant_basic.hpp"

namespace SplayTreeNodes {
template <typename Y>
struct Node_Piecewise_Constant_Basic {
  struct S {
    ll x1, x2;  // y on [x1,x2)
    Y y;
    Border_Type c1, c2;
  };
  using value_type = S;
  using operator_type = int;
  using Y_type = Y;
  using np = Node_Piecewise_Constant_Basic*;

  np p, l, r;
  bool rev;
  S x;
  u32 size;
  ll& x1() { return x.x1; }
  ll& x2() { return x.x2; }
  Border_Type& c1() { return x.c1; }
  Border_Type& c2() { return x.c2; }
  Y& y() { return x.y; }

  int lsize() { return (l ? l->size : 0); }
  int rsize() { return (r ? r->size : 0); }

  static void new_node(np n, const S& x) {
    n->p = n->l = n->r = nullptr;
    n->x = x, n->size = 1, n->rev = 0;
  }

  void update() { size = 1 + lsize() + rsize(); }

  void push() {
    if (rev) {
      if (l) {
        l->rev ^= 1, swap(l->l, l->r);
      }
      if (r) {
        r->rev ^= 1, swap(r->l, r->r);
      }
      rev = 0;
    }
  }

  // update, push 以外で呼ばれるものは、splay 後であることが想定されている。
  // したがってその時点で update, push 済であることを仮定してよい。
  S get() { return x; }
  void set(const S& xx) {
    x = xx;
    update();
  }
  void reverse() {
    swap(l, r);
    rev ^= 1;
  }
};
template <typename Y>
using Piecewise_Constant_Basic =
    Piecewise_Constant<Node_Piecewise_Constant_Basic<Y>>;
}  // namespace SplayTreeNodes

using SplayTreeNodes::Piecewise_Constant_Basic;
Back to top page