ds/segtree/range_add_make_increasing.hpp

• View this file on GitHub
• Last update: 2024-10-28 19:23:56+09:00
• Include: #include "ds/segtree/range_add_make_increasing.hpp"
• Link: https://atcoder.jp/contests/joisc2019/tasks/joisc2019_e
• Link: https://atcoder.jp/contests/joisp2024/tasks/joisp2024_i

Depends on

• alg/monoid/add.hpp
• ds/fastset.hpp
• ds/segtree/dual_segtree.hpp

Code

#include "ds/segtree/dual_segtree.hpp"
#include "alg/monoid/add.hpp"
#include "ds/fastset.hpp"

// 区間加算 / ある範囲を prefix 側から単調(増加/減少)になるように修正
// 指定しなかった場合 0 埋めで初期化される
// https://atcoder.jp/contests/joisc2019/tasks/joisc2019_e
// https://atcoder.jp/contests/joisp2024/tasks/joisp2024_i
struct Range_Add_Make_Monotonic_Increasing {
  // 代表点の集合を持つ. 代表点に対する値を双対セグ木で持つ.
  // A[i-1]>A[i] となっている i 全体も持つ.
  int n;
  FastSet S, DEC;
  Dual_SegTree<Monoid_Add<ll>> seg;

  Range_Add_Make_Monotonic_Increasing() {}
  Range_Add_Make_Monotonic_Increasing(int n) { build(n); }
  template <typename F>
  Range_Add_Make_Monotonic_Increasing(int n, F f) {
    build(n, f);
  }
  Range_Add_Make_Monotonic_Increasing(const vi& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> ll { return 0; });
  }
  template <typename F>
  void build(int m, F f) {
    vi v(m);
    FOR(i, m) v[i] = f(i);
    build(v);
  }
  void build(const vi& v) {
    n = len(v);
    seg.build(n, [&](int i) -> ll { return v[i]; }), S.build(n), DEC.build(n + 1);
    FOR(i, n) S.insert(i);
    FOR(i, 1, n) if (v[i - 1] > v[i]) DEC.insert(i);
  }

  ll get(int i) { return seg.get(S.prev(i)); }
  vi get_all() {
    auto A = seg.get_all();
    int p = 0;
    FOR(i, n) {
      if (S[i]) p = i;
      A[i] = A[p];
    }
    return A;
  }
  void set(int i, ll x) {
    split(i), split(i + 1);
    seg.set(i, x);
    DEC.insert(i), DEC.insert(i + 1);
  }
  void range_add(int L, int R, ll x) {
    split(L), split(R);
    if (x < 0) DEC.insert(L);
    if (x > 0) DEC.insert(R);
    seg.apply(L, R, x);
  }
  void range_assign(int L, int R, ll x) {
    split(L), split(R);
    INC.insert(L), INC.insert(R);
    S.enumerate(L, R, [&](int i) -> void { S.erase(i); });
    S.insert(L);
    seg.set(L, x);
  }
  void make_increasing(int L, int R) {
    split(L), split(R);
    DEC.enumerate(L + 1, R, [&](int i) -> void {
      ll mx = get(i - 1);
      while (i < R) {
        DEC.erase(i);
        ll now = get(i);
        if (mx < now) break;
        S.erase(i);
        i = S.next(i);
      }
    });
  }

private:
  void split(int p) {
    if (p == 0 || p == n || S[p]) return;
    seg.set(p, get(p));
    S.insert(p);
  }
};

#line 1 "ds/segtree/range_add_make_increasing.hpp"

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

template <typename Monoid>
struct Dual_SegTree {
  using MA = Monoid;
  using A = typename MA::value_type;
  int n, log, size;
  vc<A> laz;

  Dual_SegTree() : Dual_SegTree(0) {}
  Dual_SegTree(int n) {
    build(n, [&](int i) -> A { return MA::unit(); });
  }
  template <typename F>
  Dual_SegTree(int n, F f) {
    build(n, f);
  }

  template <typename F>
  void build(int m, F f) {
    n = m;
    log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    laz.assign(size << 1, MA::unit());
    FOR(i, n) laz[size + i] = f(i);
  }
  void build(int n) {
    build(n, [&](int i) -> A { return MA::unit(); });
  }

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

  vc<A> get_all() {
    FOR(i, size) push(i);
    return {laz.begin() + size, laz.begin() + size + n};
  }

  void set(int p, A x) {
    get(p);
    laz[p + size] = x;
  }

  void apply(int l, int r, const A& a) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return;
    l += size, r += size;
    if (!MA::commute) {
      for (int i = log; i >= 1; i--) {
        if (((l >> i) << i) != l) push(l >> i);
        if (((r >> i) << i) != r) push((r - 1) >> i);
      }
    }
    while (l < r) {
      if (l & 1) all_apply(l++, a);
      if (r & 1) all_apply(--r, a);
      l >>= 1, r >>= 1;
    }
  }

private:
  void push(int k) {
    if (laz[k] == MA::unit()) return;
    all_apply(2 * k, laz[k]), all_apply(2 * k + 1, laz[k]);
    laz[k] = MA::unit();
  }
  void all_apply(int k, A a) { laz[k] = MA::op(laz[k], a); }
};
#line 2 "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 unit() { return X(0); }
  static constexpr bool commute = true;
};
#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) {
    assert(0 <= i && i < n);
    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) {
    assert(0 <= i && i < n);
    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 5 "ds/segtree/range_add_make_increasing.hpp"

// 区間加算 / ある範囲を prefix 側から単調(増加/減少)になるように修正
// 指定しなかった場合 0 埋めで初期化される
// https://atcoder.jp/contests/joisc2019/tasks/joisc2019_e
// https://atcoder.jp/contests/joisp2024/tasks/joisp2024_i
struct Range_Add_Make_Monotonic_Increasing {
  // 代表点の集合を持つ. 代表点に対する値を双対セグ木で持つ.
  // A[i-1]>A[i] となっている i 全体も持つ.
  int n;
  FastSet S, DEC;
  Dual_SegTree<Monoid_Add<ll>> seg;

  Range_Add_Make_Monotonic_Increasing() {}
  Range_Add_Make_Monotonic_Increasing(int n) { build(n); }
  template <typename F>
  Range_Add_Make_Monotonic_Increasing(int n, F f) {
    build(n, f);
  }
  Range_Add_Make_Monotonic_Increasing(const vi& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> ll { return 0; });
  }
  template <typename F>
  void build(int m, F f) {
    vi v(m);
    FOR(i, m) v[i] = f(i);
    build(v);
  }
  void build(const vi& v) {
    n = len(v);
    seg.build(n, [&](int i) -> ll { return v[i]; }), S.build(n), DEC.build(n + 1);
    FOR(i, n) S.insert(i);
    FOR(i, 1, n) if (v[i - 1] > v[i]) DEC.insert(i);
  }

  ll get(int i) { return seg.get(S.prev(i)); }
  vi get_all() {
    auto A = seg.get_all();
    int p = 0;
    FOR(i, n) {
      if (S[i]) p = i;
      A[i] = A[p];
    }
    return A;
  }
  void set(int i, ll x) {
    split(i), split(i + 1);
    seg.set(i, x);
    DEC.insert(i), DEC.insert(i + 1);
  }
  void range_add(int L, int R, ll x) {
    split(L), split(R);
    if (x < 0) DEC.insert(L);
    if (x > 0) DEC.insert(R);
    seg.apply(L, R, x);
  }
  void range_assign(int L, int R, ll x) {
    split(L), split(R);
    INC.insert(L), INC.insert(R);
    S.enumerate(L, R, [&](int i) -> void { S.erase(i); });
    S.insert(L);
    seg.set(L, x);
  }
  void make_increasing(int L, int R) {
    split(L), split(R);
    DEC.enumerate(L + 1, R, [&](int i) -> void {
      ll mx = get(i - 1);
      while (i < R) {
        DEC.erase(i);
        ll now = get(i);
        if (mx < now) break;
        S.erase(i);
        i = S.next(i);
      }
    });
  }

private:
  void split(int p) {
    if (p == 0 || p == n || S[p]) return;
    seg.set(p, get(p));
    S.insert(p);
  }
};

Back to top page