Segment Tree Beats (chmin + chmax + add + sum)

Code

#include <vector>
#include <limits>
using i64 = long long;

struct segment_tree_chminmaxadd_rsq {
  using T = i64;

  const T ide = 0;
  static const T INF = std::numeric_limits<T>::max();
  static const T NINF = std::numeric_limits<T>::min();

  struct node {
    T sum;
    T gst1, gst2, gcnt;
    T lst1, lst2, lcnt;
    i64 len;
    i64 add;
    node(): gst2(NINF), gcnt(1), lst2(INF), lcnt(1), len(1), add(0) {}
  };

  std::vector<node> v;

  i64 n;
  i64 h;

  void fix(int k) {
    node& p = v[k];
    node& l = v[k * 2 + 0];
    node& r = v[k * 2 + 1];
    p.sum = l.sum + r.sum;

    if(r.gst1 < l.gst1) {
      p.gst1 = l.gst1;
      p.gcnt = l.gcnt;
      p.gst2 = std::max(l.gst2, r.gst1);
    }
    else if(l.gst1 < r.gst1) {
      p.gst1 = r.gst1;
      p.gcnt = r.gcnt;
      p.gst2 = std::max(l.gst1, r.gst2);
    }
    else {
      p.gst1 = l.gst1;
      p.gcnt = l.gcnt + r.gcnt;
      p.gst2 = std::max(l.gst2, r.gst2);
    }

    if(r.lst1 > l.lst1) {
      p.lst1 = l.lst1;
      p.lcnt = l.lcnt;
      p.lst2 = std::min(l.lst2, r.lst1);
    }
    else if(l.lst1 > r.lst1) {
      p.lst1 = r.lst1;
      p.lcnt = r.lcnt;
      p.lst2 = std::min(l.lst1, r.lst2);
    }
    else {
      p.lst1 = l.lst1;
      p.lcnt = l.lcnt + r.lcnt;
      p.lst2 = std::min(l.lst2, r.lst2);
    }

  }

  segment_tree_chminmaxadd_rsq() {}
  segment_tree_chminmaxadd_rsq(const std::vector<i64>& vec) {
    n = 1;
    h = 1;
    while(n < vec.size()) n <<= 1, h++;
    v.resize(2 * n);
    for(i64 i = 0;i < vec.size();i++) {
      v[i + n].sum = vec[i];
      v[i + n].gst1 = vec[i];
      v[i + n].lst1 = vec[i];
    }
    for(i64 i = n; i --> 1;) {
      fix(i);
      v[i].len = v[i * 2 + 0].len + v[i * 2 + 1].len;
    }
  }

  void eff_add(int k, T x) {
    auto& p = v[k];
    p.sum  += x * p.len;
    p.gst1 += x;
    p.lst1 += x;
    p.add += x;
    if(p.gst2 != NINF) p.gst2 += x;
    if(p.lst2 !=  INF) p.lst2 += x;
  }

  void eff_chmin(int k, T x) {
    auto& p = v[k];
    p.sum += (x - p.gst1) * p.gcnt;
    if(p.gst1 == p.lst1) {
      p.gst1 = p.lst1 = x;
    }
    else if(p.gst1 == p.lst2) {
      p.gst1 = p.lst2 = x;
    }
    else {
      p.gst1 = x;
    }
  }

  void eff_chmax(int k, T x) {
    auto& p = v[k];
    p.sum += (x - p.lst1) * p.lcnt;
    if(p.lst1 == p.gst1) {
      p.lst1 = p.gst1 = x;
    }
    else if(p.lst1 == p.gst2) {
      p.lst1 = p.gst2 = x;
    }
    else {
      p.lst1 = x;
    }
  }

  void push(int k) {
    if(k >= n) return;
    auto& p = v[k];
    if(p.add != 0) {
      eff_add(k * 2 + 0, p.add);
      eff_add(k * 2 + 1, p.add);
      p.add = 0;
    }
    if(p.gst1 < v[k * 2 + 0].gst1) eff_chmin(k * 2 + 0, p.gst1);
    if(p.gst1 < v[k * 2 + 1].gst1) eff_chmin(k * 2 + 1, p.gst1);

    if(p.lst1 > v[k * 2 + 0].lst1) eff_chmax(k * 2 + 0, p.lst1);
    if(p.lst1 > v[k * 2 + 1].lst1) eff_chmax(k * 2 + 1, p.lst1);
  }

  void infuse(int k) {
    k = k >> __builtin_ctz(k);
    while(k >>= 1) fix(k);
  }

  inline void infiltrate(int k) {
    if(k == n << 1) return;
    int kc = __builtin_ctz(k);
    for(int i = h; i --> kc;) push(k >> i);
  }

  inline void infiltrate(int l, int r) {
    if(r == n << 1) infiltrate(l);
    else {
      int hh = h;
      int x = l ^ r;
      for(; !(x >> --hh) && hh;) push(l >> hh);
      int lc = __builtin_ctz(l);
      for(int i = hh + 1; i --> lc;) push(l >> i);
      int rc = __builtin_ctz(r);
      for(int i = hh + 1; i --> rc;) push(r >> i);
    }
  }

  void subtree_chmin(int k, T x) {
    if(v[k].gst1 <= x) return;
    if(v[k].gst2 < x) {
      eff_chmin(k, x);
      return;
    }
    push(k);
    subtree_chmin(k * 2 + 0, x);
    subtree_chmin(k * 2 + 1, x);
    fix(k);
  }

  void subtree_chmax(int k, T x) {
    if(x <= v[k].lst1) return;
    if(x < v[k].lst2) {
      eff_chmax(k, x);
      return;
    }
    push(k);
    subtree_chmax(k * 2 + 0, x);
    subtree_chmax(k * 2 + 1, x);
    fix(k);
  }

  void range_chmin(int a, int b, T x) {
    int l = a + n;
    int r = b + n;
    infiltrate(l, r);
    while(l < r) {
      if(l & 1) subtree_chmin(l++, x);
      if(r & 1) subtree_chmin(--r, x);
      l >>= 1;
      r >>= 1;
    }
    infuse(a + n);
    infuse(b + n);
  }

  void range_chmax(int a, int b, T x) {
    int l = a + n;
    int r = b + n;
    infiltrate(l, r);
    while(l < r) {
      if(l & 1) subtree_chmax(l++, x);
      if(r & 1) subtree_chmax(--r, x);
      l >>= 1;
      r >>= 1;
    }
    infuse(a + n);
    infuse(b + n);
  }

  void range_add(int a, int b, T x) {
    int l = a + n;
    int r = b + n;
    infiltrate(l, r);
    while(l < r) {
      if(l & 1) eff_add(l++, x);
      if(r & 1) eff_add(--r, x);
      l >>= 1;
      r >>= 1;
    }
    infuse(a + n);
    infuse(b + n);
  }

  T range_sum(int l, int r) {
    l += n;
    r += n;
    infiltrate(l, r);
    T lx = ide;
    T rx = ide;
    while(l < r) {
      if(l & 1) lx = lx + v[l++].sum;
      if(r & 1) rx = v[--r].sum + rx;
      l >>= 1;
      r >>= 1;
    }
    return lx + rx;
  }
};