ds/rmq/range_add_range_max.hpp

• View this file on GitHub
• Last update: 2025-10-13 19:00:48+09:00
• Include: #include "ds/rmq/range_add_range_max.hpp"
• Link: https://codeforces.com/contest/542/problem/B

Depends on

• ds/segtree/dynamic_segtree_sparse.hpp
• ds/segtree/segtree.hpp

Verified with

• test/1_mytest/range_add_range_max.test.cpp

Code

#include "ds/segtree/dynamic_segtree_sparse.hpp"
#include "ds/segtree/segtree.hpp"

// INF+x==INF みたいな処理は入れていない
// N=Q=10^6 で lazysegtree より 40% 程度高速
template <typename T>
struct Range_Add_Range_Max {
  struct Mono {
    using value_type = pair<T, T>;
    using X = value_type;
    static X op(X L, X R) { return {L.fi + R.fi, max(L.se, L.fi + R.se)}; }
    static constexpr X unit() { return {0, -2 * infty<T>}; }
    static constexpr bool commute = false;
  };
  int n;
  T lazy;
  SegTree<Mono> seg;

  Range_Add_Range_Max() {}
  // (n) だけだと 0 埋めで初期化します
  Range_Add_Range_Max(int n) { build(n); }
  template <typename F>
  Range_Add_Range_Max(int n, F f) {
    build(n, f);
  }
  Range_Add_Range_Max(const vc<T> &v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> T { return 0; });
  }
  void build(const vc<T> &v) {
    build(len(v), [&](int i) -> T { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    lazy = 0;
    n = m;
    T pre = 0;
    seg.build(n, [&](int i) -> pair<T, T> {
      T t = f(i) - pre;
      pre += t;
      return {t, t};
    });
  }

  T prod(int L, int R) {
    if (L == R) return -infty<T>;
    ll ans = seg.prod(L, R).se;
    L += seg.size;
    for (; L > 0; L /= 2) {
      if (L & 1) ans += seg.dat[--L].fi;
    }
    return ans + lazy;
  }

  T prod_all() { return prod(0, n); }

  // 基本デバッグ用というつもりでさぼり O(NlogN) になっている
  vc<T> get_all() {
    vc<T> ANS(n);
    FOR(i, n) ANS[i] = prod(i, i + 1);
    return ANS;
  }

  void apply(int L, int R, T x) { apply_suffix(L, x), apply_suffix(R, -x); }

  // [0,i)
  void apply_prefix(int i, T x) {
    lazy += x;
    apply_suffix(i, -x);
  }

  // [i,n)
  void apply_suffix(int i, T x) {
    if (i == n) return;
    T t = seg.get(i).fi + x;
    seg.set(i, {t, t});
  }
  void apply_all(T x) { lazy += x; }

  void set(int i, T x) {
    T now = prod(i, i + 1);
    apply(i, i + 1, x - now);
  }

  void multiply(int i, T x) {
    T now = prod(i, i + 1);
    if (now < x) apply(i, i + 1, x - now);
  }
};

// 座標は long long. ほぼ verify されていない
// https://codeforces.com/contest/542/problem/B
template <typename T>
struct Dynamic_Range_Add_Range_Max {
  struct Mono {
    using value_type = pair<T, T>;
    using X = value_type;
    static X op(X L, X R) { return {L.fi + R.fi, max(L.se, L.fi + R.se)}; }
    static constexpr X unit() { return {0, 0}; }
    static constexpr bool commute = false;
  };
  int n;
  Dynamic_SegTree_Sparse<Mono, false> seg;
  T lazy;
  using np = typename decltype(seg)::np;
  np root;

  // range apply * 2 くらいのノード数
  Dynamic_Range_Add_Range_Max(int NODES, ll L, ll R)
      : seg(NODES, L, R), lazy(0) {
    root = seg.new_root();
  }

  T prod(ll L, ll R) {
    if (L == R) return -infty<T>;
    ll ans = seg.prod(root, L, R).se;
    ans += seg.prod(root, seg.L0, L).fi;
    return ans + lazy;
  }

  void apply(ll L, ll R, T x) { apply_suffix(L, x), apply_suffix(R, -x); }

  // [i,n)
  void apply_suffix(ll i, T x) {
    if (i == seg.R0) return;
    T t = seg.get(root, i).fi + x;
    root = seg.set(root, i, {t, t});
  }
  void apply_all(T x) { lazy += x; }
};

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

// 常にほとんどの要素が unit であることが保証されるような動的セグ木
// したがって、default_prod の類は持たせられず、acted monoid も一般には扱えない
// 追加 N 回のときノード数 N 以下が保証される
template <typename Monoid, bool PERSISTENT>
struct Dynamic_SegTree_Sparse {
  using MX = Monoid;
  using X = typename MX::value_type;

  struct Node {
    int ch[2];
    ll idx;
    X prod, x;
  };
  const ll L0, R0;
  static constexpr int NIL = 0;
  vc<Node> node;
  vc<int> FREE;

  Dynamic_SegTree_Sparse(ll L0, ll R0) : L0(L0), R0(R0) { reset(); }
  void reserve(int n) { node.reserve(n + 1); }
  void reset() {
    node.clear(), FREE.clear();
    node.eb(Node{{NIL, NIL}, 0, MX::unit(), MX::unit()});  // NIL
  }

  // 木 dp のマージのときなどに使用すると MLE 回避できることがある
  // https://codeforces.com/problemset/problem/671/D
  void free_subtree(int c) {
    assert(c != NIL);
    auto dfs = [&](auto &dfs, int c) -> void {
      if (c == NIL) return;
      dfs(dfs, node[c].ch[0]), dfs(dfs, node[c].ch[1]);
      FREE.eb(c);
    };
    dfs(dfs, c);
  }

  inline int new_root() { return NIL; }

  inline int new_node(ll idx, const X x) {
    if (!FREE.empty()) {
      int id = POP(FREE);
      node[id].ch[0] = node[id].ch[1] = NIL;
      node[id].idx = idx, node[id].x = x, node[id].prod = x;
      return id;
    }
    node.eb(Node{{NIL, NIL}, idx, x, x});
    return int(node.size()) - 1;
  }
  inline Node operator[](int i) const { return node[i]; }

  X prod(int root, ll l, ll r) {
    assert(L0 <= l && l <= r && r <= R0);
    if (root == NIL || l == r) return MX::unit();
    X x = MX::unit();
    prod_rec(root, L0, R0, l, r, x);
    return x;
  }

  X prod_all(int root) { return (root == NIL ? MX::unit() : node[root].prod); }

  int set(int root, ll i, const X &x) {
    assert(L0 <= i && i < R0);
    return set_rec(root, L0, R0, i, x);
  }

  int multiply(int root, ll i, const X &x) {
    assert(L0 <= i && i < R0);
    return multiply_rec(root, L0, R0, i, x);
  }

  template <typename F>
  ll max_right(int root, F check, ll L) {
    assert(L0 <= L && L <= R0 && check(MX::unit()));
    X x = MX::unit();
    return max_right_rec(root, check, L0, R0, L, x);
  }

  template <typename F>
  ll min_left(int root, F check, ll R) {
    assert(L0 <= R && R <= R0 && check(MX::unit()));
    X x = MX::unit();
    return min_left_rec(root, check, L0, R0, R, x);
  }

  vc<pair<ll, X>> get_all(int root) {
    vc<pair<ll, X>> res;
    auto dfs = [&](auto &dfs, int c) -> void {
      if (c == NIL) return;
      dfs(dfs, node[c].ch[0]);
      res.eb(node[c].idx, node[c].x);
      dfs(dfs, node[c].ch[1]);
    };
    dfs(dfs, root);
    return res;
  }

  X get(int root, ll idx) {
    auto dfs = [&](auto &dfs, int c) -> X {
      if (c == NIL) return MX::unit();
      if (idx == node[c].idx) return node[c].x;
      return dfs(dfs, node[c].ch[idx > node[c].idx]);
    };
    return dfs(dfs, root);
  }

 private:
  inline void update(int c) {
    node[c].prod = node[c].x;
    node[c].prod = MX::op(node[node[c].ch[0]].prod, node[c].prod);
    node[c].prod = MX::op(node[c].prod, node[node[c].ch[1]].prod);
  }

  inline int clone(int c) {
    if constexpr (!PERSISTENT)
      return c;
    else {
      if (c == NIL) return c;
      node.eb(node[c]);
      return int(node.size()) - 1;
    }
  }

  int set_rec(int c, ll l, ll r, ll i, X x) {
    if (c == NIL) return new_node(i, x);
    c = clone(c);
    if (node[c].idx == i) {
      node[c].x = x;
      update(c);
      return c;
    }
    ll m = (l + r) / 2;
    if (i < m) {
      if (node[c].idx < i) swap(node[c].idx, i), swap(node[c].x, x);
      node[c].ch[0] = set_rec(node[c].ch[0], l, m, i, x);
    }
    if (m <= i) {
      if (i < node[c].idx) swap(node[c].idx, i), swap(node[c].x, x);
      node[c].ch[1] = set_rec(node[c].ch[1], m, r, i, x);
    }
    update(c);
    return c;
  }

  int multiply_rec(int c, ll l, ll r, ll i, X x) {
    if (c == NIL) return new_node(i, x);
    c = clone(c);
    if (node[c].idx == i) {
      node[c].x = MX::op(node[c].x, x);
      update(c);
      return c;
    }
    ll m = (l + r) / 2;
    if (i < m) {
      if (node[c].idx < i) swap(node[c].idx, i), swap(node[c].x, x);
      node[c].ch[0] = multiply_rec(node[c].ch[0], l, m, i, x);
    }
    if (m <= i) {
      if (i < node[c].idx) swap(node[c].idx, i), swap(node[c].x, x);
      node[c].ch[1] = multiply_rec(node[c].ch[1], m, r, i, x);
    }
    update(c);
    return c;
  }

  void prod_rec(int c, ll l, ll r, ll ql, ll qr, X &x) {
    chmax(ql, l);
    chmin(qr, r);
    if (ql >= qr || c == NIL) return;
    if (l == ql && r == qr) {
      x = MX::op(x, node[c].prod);
      return;
    }
    ll m = (l + r) / 2;
    prod_rec(node[c].ch[0], l, m, ql, qr, x);
    if (ql <= (node[c].idx) && (node[c].idx) < qr) x = MX::op(x, node[c].x);
    prod_rec(node[c].ch[1], m, r, ql, qr, x);
  }

  template <typename F>
  ll max_right_rec(int c, const F &check, ll l, ll r, ll ql, X &x) {
    if (c == NIL || r <= ql) return R0;
    if (check(MX::op(x, node[c].prod))) {
      x = MX::op(x, node[c].prod);
      return R0;
    }
    ll m = (l + r) / 2;
    ll k = max_right_rec(node[c].ch[0], check, l, m, ql, x);
    if (k != R0) return k;
    if (ql <= node[c].idx) {
      x = MX::op(x, node[c].x);
      if (!check(x)) return node[c].idx;
    }
    return max_right_rec(node[c].ch[1], check, m, r, ql, x);
  }

  template <typename F>
  ll min_left_rec(int c, const F &check, ll l, ll r, ll qr, X &x) {
    if (c == NIL || qr <= l) return L0;
    if (check(MX::op(node[c].prod, x))) {
      x = MX::op(node[c].prod, x);
      return L0;
    }
    ll m = (l + r) / 2;
    ll k = min_left_rec(node[c].ch[1], check, m, r, qr, x);
    if (k != L0) return k;
    if (node[c].idx < qr) {
      x = MX::op(node[c].x, x);
      if (!check(x)) return node[c].idx + 1;
    }
    return min_left_rec(node[c].ch[0], check, l, m, qr, x);
  }
};
#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);
  }

  vc<int> prod_ids(int L, int R) {
    assert(0 <= L && L <= R && R <= n);
    vc<int> I, J;
    L += size, R += size;
    while (L < R) {
      if (L & 1) I.eb(L++);
      if (R & 1) J.eb(--R);
      L >>= 1, R >>= 1;
    }
    reverse(all(J));
    concat(I, J);
    return I;
  }

  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 3 "ds/rmq/range_add_range_max.hpp"

// INF+x==INF みたいな処理は入れていない
// N=Q=10^6 で lazysegtree より 40% 程度高速
template <typename T>
struct Range_Add_Range_Max {
  struct Mono {
    using value_type = pair<T, T>;
    using X = value_type;
    static X op(X L, X R) { return {L.fi + R.fi, max(L.se, L.fi + R.se)}; }
    static constexpr X unit() { return {0, -2 * infty<T>}; }
    static constexpr bool commute = false;
  };
  int n;
  T lazy;
  SegTree<Mono> seg;

  Range_Add_Range_Max() {}
  // (n) だけだと 0 埋めで初期化します
  Range_Add_Range_Max(int n) { build(n); }
  template <typename F>
  Range_Add_Range_Max(int n, F f) {
    build(n, f);
  }
  Range_Add_Range_Max(const vc<T> &v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> T { return 0; });
  }
  void build(const vc<T> &v) {
    build(len(v), [&](int i) -> T { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    lazy = 0;
    n = m;
    T pre = 0;
    seg.build(n, [&](int i) -> pair<T, T> {
      T t = f(i) - pre;
      pre += t;
      return {t, t};
    });
  }

  T prod(int L, int R) {
    if (L == R) return -infty<T>;
    ll ans = seg.prod(L, R).se;
    L += seg.size;
    for (; L > 0; L /= 2) {
      if (L & 1) ans += seg.dat[--L].fi;
    }
    return ans + lazy;
  }

  T prod_all() { return prod(0, n); }

  // 基本デバッグ用というつもりでさぼり O(NlogN) になっている
  vc<T> get_all() {
    vc<T> ANS(n);
    FOR(i, n) ANS[i] = prod(i, i + 1);
    return ANS;
  }

  void apply(int L, int R, T x) { apply_suffix(L, x), apply_suffix(R, -x); }

  // [0,i)
  void apply_prefix(int i, T x) {
    lazy += x;
    apply_suffix(i, -x);
  }

  // [i,n)
  void apply_suffix(int i, T x) {
    if (i == n) return;
    T t = seg.get(i).fi + x;
    seg.set(i, {t, t});
  }
  void apply_all(T x) { lazy += x; }

  void set(int i, T x) {
    T now = prod(i, i + 1);
    apply(i, i + 1, x - now);
  }

  void multiply(int i, T x) {
    T now = prod(i, i + 1);
    if (now < x) apply(i, i + 1, x - now);
  }
};

// 座標は long long. ほぼ verify されていない
// https://codeforces.com/contest/542/problem/B
template <typename T>
struct Dynamic_Range_Add_Range_Max {
  struct Mono {
    using value_type = pair<T, T>;
    using X = value_type;
    static X op(X L, X R) { return {L.fi + R.fi, max(L.se, L.fi + R.se)}; }
    static constexpr X unit() { return {0, 0}; }
    static constexpr bool commute = false;
  };
  int n;
  Dynamic_SegTree_Sparse<Mono, false> seg;
  T lazy;
  using np = typename decltype(seg)::np;
  np root;

  // range apply * 2 くらいのノード数
  Dynamic_Range_Add_Range_Max(int NODES, ll L, ll R)
      : seg(NODES, L, R), lazy(0) {
    root = seg.new_root();
  }

  T prod(ll L, ll R) {
    if (L == R) return -infty<T>;
    ll ans = seg.prod(root, L, R).se;
    ans += seg.prod(root, seg.L0, L).fi;
    return ans + lazy;
  }

  void apply(ll L, ll R, T x) { apply_suffix(L, x), apply_suffix(R, -x); }

  // [i,n)
  void apply_suffix(ll i, T x) {
    if (i == seg.R0) return;
    T t = seg.get(root, i).fi + x;
    root = seg.set(root, i, {t, t});
  }
  void apply_all(T x) { lazy += x; }
};

Back to top page