ds/segtree/range_assignment_segtree.hpp

• View this file on GitHub
• Last update: 2024-04-27 11:55:26+09:00
• Include: #include "ds/segtree/range_assignment_segtree.hpp"

Depends on

• alg/monoid_pow.hpp
• ds/fastset.hpp
• ds/segtree/segtree.hpp

Verified with

• test/library_checker/datastructure/range_set_range_composite.test.cpp
• test/mytest/range_assign.test.cpp

Code

#include "ds/segtree/segtree.hpp"
#include "alg/monoid_pow.hpp"
#include "ds/fastset.hpp"

template <typename Monoid>
struct Range_Assignment_SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n;
  SegTree<MX> seg;
  FastSet cut;
  vc<X> dat;

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

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  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;
    seg.build(m, f), cut.build(n, [&](int i) -> int { return 1; });
    dat = seg.get_all();
  }

  X prod(int l, int r) {
    int a = cut.prev(l), b = cut.next(l), c = cut.prev(r);
    if (a == c) { return monoid_pow<MX>(dat[a], r - l); };
    assert(b <= c);
    X x = monoid_pow<MX>(dat[a], b - l);
    X y = seg.prod(b, c);
    X z = monoid_pow<MX>(dat[c], r - c);
    return MX::op(MX::op(x, y), z);
  }

  void assign(int l, int r, X x) {
    int a = cut.prev(l), b = cut.next(r);
    if (a < l) seg.set(a, monoid_pow<MX>(dat[a], l - a));
    if (r < b) {
      X y = dat[cut.prev(r)];
      dat[r] = y, cut.insert(r), seg.set(r, monoid_pow<MX>(y, b - r));
    }
    cut.enumerate(l + 1, r,
                  [&](int i) -> void { seg.set(i, MX::unit()), cut.erase(i); });
    dat[l] = x, cut.insert(l), seg.set(l, monoid_pow<MX>(x, r - l));
  }
};

#line 2 "ds/segtree/segtree.hpp"

template <class Monoid>
struct SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  using value_type = X;
  vc<X> dat;
  int n, log, size;

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

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  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 = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::unit());
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  X get(int i) { return dat[size + i]; }
  vc<X> get_all() { return {dat.begin() + size, dat.begin() + size + n}; }

  void update(int i) { dat[i] = Monoid::op(dat[2 * i], dat[2 * i + 1]); }
  void set(int i, const X& x) {
    assert(i < n);
    dat[i += size] = x;
    while (i >>= 1) update(i);
  }

  void multiply(int i, const X& x) {
    assert(i < n);
    i += size;
    dat[i] = Monoid::op(dat[i], x);
    while (i >>= 1) update(i);
  }

  X prod(int L, int R) {
    assert(0 <= L && L <= R && R <= n);
    X vl = Monoid::unit(), vr = Monoid::unit();
    L += size, R += size;
    while (L < R) {
      if (L & 1) vl = Monoid::op(vl, dat[L++]);
      if (R & 1) vr = Monoid::op(dat[--R], vr);
      L >>= 1, R >>= 1;
    }
    return Monoid::op(vl, vr);
  }

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

  template <class F>
  int max_right(F check, int L) {
    assert(0 <= L && L <= n && check(Monoid::unit()));
    if (L == n) return n;
    L += size;
    X sm = Monoid::unit();
    do {
      while (L % 2 == 0) L >>= 1;
      if (!check(Monoid::op(sm, dat[L]))) {
        while (L < size) {
          L = 2 * L;
          if (check(Monoid::op(sm, dat[L]))) { sm = Monoid::op(sm, dat[L++]); }
        }
        return L - size;
      }
      sm = Monoid::op(sm, dat[L++]);
    } while ((L & -L) != L);
    return n;
  }

  template <class F>
  int min_left(F check, int R) {
    assert(0 <= R && R <= n && check(Monoid::unit()));
    if (R == 0) return 0;
    R += size;
    X sm = Monoid::unit();
    do {
      --R;
      while (R > 1 && (R % 2)) R >>= 1;
      if (!check(Monoid::op(dat[R], sm))) {
        while (R < size) {
          R = 2 * R + 1;
          if (check(Monoid::op(dat[R], sm))) { sm = Monoid::op(dat[R--], sm); }
        }
        return R + 1 - size;
      }
      sm = Monoid::op(dat[R], sm);
    } while ((R & -R) != R);
    return 0;
  }

  // prod_{l<=i<r} A[i xor x]
  X xor_prod(int l, int r, int xor_val) {
    static_assert(Monoid::commute);
    X x = Monoid::unit();
    for (int k = 0; k < log + 1; ++k) {
      if (l >= r) break;
      if (l & 1) { x = Monoid::op(x, dat[(size >> k) + ((l++) ^ xor_val)]); }
      if (r & 1) { x = Monoid::op(x, dat[(size >> k) + ((--r) ^ xor_val)]); }
      l /= 2, r /= 2, xor_val /= 2;
    }
    return x;
  }
};
#line 2 "alg/monoid_pow.hpp"

// chat gpt
template <typename U, typename Arg1, typename Arg2>
struct has_power_method {
private:
  // ヘルパー関数の実装
  template <typename V, typename A1, typename A2>
  static auto check(int)
      -> decltype(std::declval<V>().power(std::declval<A1>(),
                                          std::declval<A2>()),
                  std::true_type{});
  template <typename, typename, typename>
  static auto check(...) -> std::false_type;

public:
  // メソッドの有無を表す型
  static constexpr bool value = decltype(check<U, Arg1, Arg2>(0))::value;
};

template <typename Monoid>
typename Monoid::X monoid_pow(typename Monoid::X x, ll exp) {
  using X = typename Monoid::X;
  if constexpr (has_power_method<Monoid, X, ll>::value) {
    return Monoid::power(x, exp);
  } else {
    assert(exp >= 0);
    X res = Monoid::unit();
    while (exp) {
      if (exp & 1) res = Monoid::op(res, x);
      x = Monoid::op(x, x);
      exp >>= 1;
    }
    return res;
  }
}
#line 2 "ds/fastset.hpp"

// 64-ary tree

// space: (N/63) * u64

struct FastSet {
  static constexpr u32 B = 64;
  int n, log;
  vvc<u64> seg;

  FastSet() {}
  FastSet(int n) { build(n); }

  int size() { return n; }

  template <typename F>
  FastSet(int n, F f) {
    build(n, f);
  }

  void build(int m) {
    seg.clear();
    n = m;
    do {
      seg.push_back(vc<u64>((m + B - 1) / B));
      m = (m + B - 1) / B;
    } while (m > 1);
    log = len(seg);
  }
  template <typename F>
  void build(int n, F f) {
    build(n);
    FOR(i, n) { seg[0][i / B] |= u64(f(i)) << (i % B); }
    FOR(h, log - 1) {
      FOR(i, len(seg[h])) {
        seg[h + 1][i / B] |= u64(bool(seg[h][i])) << (i % B);
      }
    }
  }

  bool operator[](int i) const { return seg[0][i / B] >> (i % B) & 1; }
  void insert(int i) {
    for (int h = 0; h < log; h++) {
      seg[h][i / B] |= u64(1) << (i % B), i /= B;
    }
  }
  void add(int i) { insert(i); }
  void erase(int i) {
    u64 x = 0;
    for (int h = 0; h < log; h++) {
      seg[h][i / B] &= ~(u64(1) << (i % B));
      seg[h][i / B] |= x << (i % B);
      x = bool(seg[h][i / B]);
      i /= B;
    }
  }
  void remove(int i) { erase(i); }

  // min[x,n) or n

  int next(int i) {
    assert(i <= n);
    chmax(i, 0);
    for (int h = 0; h < log; h++) {
      if (i / B == seg[h].size()) break;
      u64 d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      i += lowbit(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += lowbit(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }

  // max [0,x], or -1

  int prev(int i) {
    assert(i >= -1);
    if (i >= n) i = n - 1;
    for (int h = 0; h < log; h++) {
      if (i == -1) break;
      u64 d = seg[h][i / B] << (63 - i % B);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      i -= __builtin_clzll(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += topbit(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }

  bool any(int l, int r) { return next(l) < r; }

  // [l, r)

  template <typename F>
  void enumerate(int l, int r, F f) {
    for (int x = next(l); x < r; x = next(x + 1)) f(x);
  }

  string to_string() {
    string s(n, '?');
    for (int i = 0; i < n; ++i) s[i] = ((*this)[i] ? '1' : '0');
    return s;
  }
};
#line 4 "ds/segtree/range_assignment_segtree.hpp"

template <typename Monoid>
struct Range_Assignment_SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n;
  SegTree<MX> seg;
  FastSet cut;
  vc<X> dat;

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

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  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;
    seg.build(m, f), cut.build(n, [&](int i) -> int { return 1; });
    dat = seg.get_all();
  }

  X prod(int l, int r) {
    int a = cut.prev(l), b = cut.next(l), c = cut.prev(r);
    if (a == c) { return monoid_pow<MX>(dat[a], r - l); };
    assert(b <= c);
    X x = monoid_pow<MX>(dat[a], b - l);
    X y = seg.prod(b, c);
    X z = monoid_pow<MX>(dat[c], r - c);
    return MX::op(MX::op(x, y), z);
  }

  void assign(int l, int r, X x) {
    int a = cut.prev(l), b = cut.next(r);
    if (a < l) seg.set(a, monoid_pow<MX>(dat[a], l - a));
    if (r < b) {
      X y = dat[cut.prev(r)];
      dat[r] = y, cut.insert(r), seg.set(r, monoid_pow<MX>(y, b - r));
    }
    cut.enumerate(l + 1, r,
                  [&](int i) -> void { seg.set(i, MX::unit()), cut.erase(i); });
    dat[l] = x, cut.insert(l), seg.set(l, monoid_pow<MX>(x, r - l));
  }
};

Back to top page