library

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

View the Project on GitHub maspypy/library

:heavy_check_mark: seq/common_interval_decomposition.hpp

Depends on

Verified with

Code

#include "ds/segtree/lazy_segtree.hpp"
#include "alg/acted_monoid/min_add.hpp"

struct Common_Interval_Decomposition {
  struct Node {
    vc<Node*> ch;
    bool inc, dec;
    int l, r, lo, hi;
    string type() {
      if (r == l + 1) return "leaf";
      if (inc) return "inc";
      if (dec) return "dec";
      return "prime";
    }
  };

  Node* pool;
  Node* root;
  int pid;

  Common_Interval_Decomposition(vc<int>& P) : pid(0) {
    pool = new Node[2 * len(P)];
    build(P);
  }

  Node* new_node(bool inc, bool dec, int l, int r, int lo, int hi) {
    pool[pid].inc = inc;
    pool[pid].dec = dec;
    pool[pid].l = l;
    pool[pid].r = r;
    pool[pid].lo = lo;
    pool[pid].hi = hi;
    return &(pool[pid++]);
  }

  void build(vc<int>& P) {
    int N = len(P);
    Lazy_SegTree<ActedMonoid_Min_Add<int>> seg(vc<int>(N, 0));

    vc<Node*> st;
    vc<int> mi = {-1}, ma = {-1};
    FOR(i, N) {
      while (mi.back() != -1 && P[i] < P[mi.back()]) {
        int j = POP(mi);
        seg.apply(mi.back() + 1, j + 1, P[j] - P[i]);
      }
      while (ma.back() != -1 && P[i] > P[ma.back()]) {
        int j = POP(ma);
        seg.apply(ma.back() + 1, j + 1, P[i] - P[j]);
      }
      mi.eb(i), ma.eb(i);

      Node* now = new_node(0, 0, i, i + 1, P[i], P[i] + 1);
      while (len(st)) {
        Node* n = st.back();
        if (n->hi == now->lo) {
          if (n->inc) {
            n->ch.eb(now);
            n->r = now->r;
            n->hi = now->hi;
            now = n;
            st.pop_back();
          } else {
            Node* p = new_node(1, 0, n->l, now->r, n->lo, now->hi);
            p->ch.eb(n);
            p->ch.eb(now);
            now = p;
            st.pop_back();
          }
          continue;
        }
        if (n->lo == now->hi) {
          if (n->dec) {
            n->ch.eb(now);
            n->r = now->r;
            n->lo = now->lo;
            now = n;
            st.pop_back();
          } else {
            Node* p = new_node(0, 1, n->l, now->r, now->lo, n->hi);
            p->ch.eb(n);
            p->ch.eb(now);
            now = p;
            st.pop_back();
          }
          continue;
        }
        // prime supernode creation
        if (seg.prod(0, now->l) != 0) break;
        Node* p = new_node(0, 0, now->l, now->r, now->lo, now->hi);
        p->ch.eb(now);
        now = p;
        while (1) {
          auto c = POP(st);
          now->l = c->l;
          chmin(now->lo, c->lo);
          chmax(now->hi, c->hi);
          now->ch.eb(c);
          if (now->r - now->l == now->hi - now->lo) break;
        }
        reverse(all(now->ch));
      }
      st.eb(now);
      seg.apply(0, i + 1, -1);
    }
    assert(len(st) == 1);
    root = POP(st);
    return;
  }

  void debug() {
    auto dfs = [&](auto& dfs, Node* n) -> void {
      print("l, r, lo, hi", n->l, n->r, n->lo, n->hi);
      for (auto&& c : n->ch) dfs(dfs, c);
    };
    dfs(dfs, root);
  };
};
#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) {
  assert(0 <= n && n <= 64);
  return n == 64 ? -1ULL : (1ULL << n) - 1;
}

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "ds/segtree/lazy_segtree.hpp"

template <typename ActedMonoid>
struct Lazy_SegTree {
  using AM = ActedMonoid;
  using MX = typename AM::Monoid_X;
  using MA = typename AM::Monoid_A;
  using X = typename MX::value_type;
  using A = typename MA::value_type;
  int n, log, size;
  vc<X> dat;
  vc<A> laz;
  vc<bool> has_laz;

  Lazy_SegTree() {}
  Lazy_SegTree(int n) { build(n); }
  template <typename F>
  Lazy_SegTree(int n, F f) {
    build(n, f);
  }
  Lazy_SegTree(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::id(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 0;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::id());
    laz.assign(size, MA::id());
    has_laz.assign(size, false);
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  void update(int k) { dat[k] = MX::op(dat[2 * k], dat[2 * k + 1]); }
  void set(int p, X x) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    dat[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void multiply(int p, const X& x) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    dat[p] = MX::op(dat[p], x);
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  X get(int p) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return dat[p];
  }

  vc<X> get_all() {
    FOR(k, 1, size) { push(k); }
    return {dat.begin() + size, dat.begin() + size + n};
  }

  X prod(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return MX::id();
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    X xl = MX::id(), xr = MX::id();
    while (l < r) {
      if (l & 1) xl = MX::op(xl, dat[l++]);
      if (r & 1) xr = MX::op(dat[--r], xr);
      l >>= 1, r >>= 1;
    }
    return MX::op(xl, xr);
  }

  X prod_all() { return dat[1]; }

  void apply(int l, int r, A a) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return;
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    int l2 = l, r2 = r;
    while (l < r) {
      if (l & 1) apply_at(l++, a);
      if (r & 1) apply_at(--r, a);
      l >>= 1, r >>= 1;
    }
    l = l2, r = r2;
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template <typename F>
  int max_right(const F check, int l) {
    assert(0 <= l && l <= n);
    assert(check(MX::id()));
    if (l == n) return n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    X sm = MX::id();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!check(MX::op(sm, dat[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (check(MX::op(sm, dat[l]))) {
            sm = MX::op(sm, dat[l++]);
          }
        }
        return l - size;
      }
      sm = MX::op(sm, dat[l++]);
    } while ((l & -l) != l);
    return n;
  }

  template <typename F>
  int min_left(const F check, int r) {
    assert(0 <= r && r <= n);
    assert(check(MX::id()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    X sm = MX::id();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(MX::op(dat[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (check(MX::op(dat[r], sm))) {
            sm = MX::op(dat[r--], sm);
          }
        }
        return r + 1 - size;
      }
      sm = MX::op(dat[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

  // l <= i xor (xor_val) < r となる i 全体に apply
  void apply_xor_range(int l, int r, int xor_val, A a) {
    assert(!(n & (n - 1)));
    assert(0 <= xor_val && xor_val < n);
    assert(0 <= l && l <= r && r <= n);

    auto dfs = [&](auto& dfs, int idx, int seg_l, int seg_r) -> void {
      if (l <= seg_l && seg_r <= r) {
        return apply_at(idx, a);
      }
      if (r <= seg_l || seg_r <= l) return;
      push(idx);
      int seg_m = (seg_l + seg_r) / 2;
      int bit = (seg_r - seg_l) / 2;
      int left = 2 * idx + 0, right = 2 * idx + 1;
      if (xor_val & bit) swap(left, right);
      dfs(dfs, left, seg_l, seg_m);
      dfs(dfs, right, seg_m, seg_r);
      update(idx);
    };
    dfs(dfs, 1, 0, n);
  }

 private:
  void apply_at(int k, A a) {
    ll sz = 1 << (log - topbit(k));
    dat[k] = AM::act(dat[k], a, sz);
    if (k < size) has_laz[k] = 1, laz[k] = MA::op(laz[k], a);
  }
  void push(int k) {
    if (!has_laz[k]) return;
    has_laz[k] = 0;
    apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
    laz[k] = MA::id();
  }
};
#line 1 "alg/monoid/add.hpp"

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X id() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "alg/monoid/min.hpp"
// require: all values x satisfy x <= infty<E>
template <typename E>
struct Monoid_Min {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return min(x, y); }
  static constexpr X id() { return infty<E>; }
  static constexpr bool commute = true;
};
#line 3 "alg/acted_monoid/min_add.hpp"

template <typename E>
struct ActedMonoid_Min_Add {
  using Monoid_X = Monoid_Min<E>;
  using Monoid_A = Monoid_Add<E>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X &x, const A &a, const ll &size) {
    if (x == infty<E>) return x;
    return x + a;
  }
};
#line 3 "seq/common_interval_decomposition.hpp"

struct Common_Interval_Decomposition {
  struct Node {
    vc<Node*> ch;
    bool inc, dec;
    int l, r, lo, hi;
    string type() {
      if (r == l + 1) return "leaf";
      if (inc) return "inc";
      if (dec) return "dec";
      return "prime";
    }
  };

  Node* pool;
  Node* root;
  int pid;

  Common_Interval_Decomposition(vc<int>& P) : pid(0) {
    pool = new Node[2 * len(P)];
    build(P);
  }

  Node* new_node(bool inc, bool dec, int l, int r, int lo, int hi) {
    pool[pid].inc = inc;
    pool[pid].dec = dec;
    pool[pid].l = l;
    pool[pid].r = r;
    pool[pid].lo = lo;
    pool[pid].hi = hi;
    return &(pool[pid++]);
  }

  void build(vc<int>& P) {
    int N = len(P);
    Lazy_SegTree<ActedMonoid_Min_Add<int>> seg(vc<int>(N, 0));

    vc<Node*> st;
    vc<int> mi = {-1}, ma = {-1};
    FOR(i, N) {
      while (mi.back() != -1 && P[i] < P[mi.back()]) {
        int j = POP(mi);
        seg.apply(mi.back() + 1, j + 1, P[j] - P[i]);
      }
      while (ma.back() != -1 && P[i] > P[ma.back()]) {
        int j = POP(ma);
        seg.apply(ma.back() + 1, j + 1, P[i] - P[j]);
      }
      mi.eb(i), ma.eb(i);

      Node* now = new_node(0, 0, i, i + 1, P[i], P[i] + 1);
      while (len(st)) {
        Node* n = st.back();
        if (n->hi == now->lo) {
          if (n->inc) {
            n->ch.eb(now);
            n->r = now->r;
            n->hi = now->hi;
            now = n;
            st.pop_back();
          } else {
            Node* p = new_node(1, 0, n->l, now->r, n->lo, now->hi);
            p->ch.eb(n);
            p->ch.eb(now);
            now = p;
            st.pop_back();
          }
          continue;
        }
        if (n->lo == now->hi) {
          if (n->dec) {
            n->ch.eb(now);
            n->r = now->r;
            n->lo = now->lo;
            now = n;
            st.pop_back();
          } else {
            Node* p = new_node(0, 1, n->l, now->r, now->lo, n->hi);
            p->ch.eb(n);
            p->ch.eb(now);
            now = p;
            st.pop_back();
          }
          continue;
        }
        // prime supernode creation
        if (seg.prod(0, now->l) != 0) break;
        Node* p = new_node(0, 0, now->l, now->r, now->lo, now->hi);
        p->ch.eb(now);
        now = p;
        while (1) {
          auto c = POP(st);
          now->l = c->l;
          chmin(now->lo, c->lo);
          chmax(now->hi, c->hi);
          now->ch.eb(c);
          if (now->r - now->l == now->hi - now->lo) break;
        }
        reverse(all(now->ch));
      }
      st.eb(now);
      seg.apply(0, i + 1, -1);
    }
    assert(len(st) == 1);
    root = POP(st);
    return;
  }

  void debug() {
    auto dfs = [&](auto& dfs, Node* n) -> void {
      print("l, r, lo, hi", n->l, n->r, n->lo, n->hi);
      for (auto&& c : n->ch) dfs(dfs, c);
    };
    dfs(dfs, root);
  };
};
Back to top page