LazySegmentTree

/*
 * Segment should have :
 * Segment()
 * Segment(arg)
 * operator +
 * push()
 * clearAfterPush()
 * apply(args...)
 */
template <typename Segment>
struct LazySegmentTree {
  int n;
  mutable std::vector<Segment> a;

  void pull(int x, int l, int r) {
    int m = l + (r - l) / 2;
    a[x] = a[x + 1] + a[x + 2 * (m - l)];
  }

  void push(int x, int l, int r) const {
    int m = l + (r - l) / 2;
    a[x].push(a[x + 1]);
    a[x].push(a[x + 2 * (m - l)]);
    a[x].clearAfterPush();
  }

  explicit LazySegmentTree(int n) {
    assert(n > 0);
    this->n = n;
    a.resize(2 * n - 1);
    auto build = [&](auto&& build, int x, int l, int r) -> void {
      if (r - l == 1) {
        return;
      }
      int m = l + (r - l) / 2;
      build(build, x + 1, l, m);
      build(build, x + 2 * (m - l), m, r);
      pull(x, l, r);
    };
    build(build, 0, 0, n);
  }

  template <typename M>
  explicit LazySegmentTree(const std::vector<M>& v) {
    assert(!v.empty());
    n = int(v.size());
    a.resize(2 * n - 1);
    auto build = [&](auto&& build, int x, int l, int r) -> void {
      if (r - l == 1) {
        a[x] = Segment(v[l]);
        return;
      }
      int m = l + (r - l) / 2;
      build(build, x + 1, l, m);
      build(build, x + 2 * (m - l), m, r);
      pull(x, l, r);
    };
    build(build, 0, 0, n);
  }

  template <typename... Types>
  void modifyImpl(int x, int l, int r, int ll, int rr, Types&&... args) {
    if (ll <= l && r <= rr) {
      a[x].apply(args...);
      return;
    }
    push(x, l, r);
    int m = l + (r - l) / 2;
    if (ll < m) {
      modifyImpl(x + 1, l, m, ll, rr, args...);
    }
    if (m < rr) {
      modifyImpl(x + 2 * (m - l), m, r, ll, rr, args...);
    }
    pull(x, l, r);
  }

  template <typename... Types>
  void modify(int ll, int rr, Types&&... args) {
    assert(0 <= ll && ll <= rr && rr <= n);
    if (ll != rr) {
      modifyImpl(0, 0, n, ll, rr, args...);
    }
  }

  Segment getImpl(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return a[x];
    }
    push(x, l, r);
    int m = l + (r - l) / 2;
    if (rr <= m) {
      return getImpl(x + 1, l, m, ll, rr);
    } else if (m <= ll) {
      return getImpl(x + 2 * (m - l), m, r, ll, rr);
    } else {
      return getImpl(x + 1, l, m, ll, rr) + getImpl(x + 2 * (m - l), m, r, ll, rr);
    }
  }

  Segment get(int ll, int rr) {
    assert(0 <= ll && ll < rr && rr <= n);
    return getImpl(0, 0, n, ll, rr);
  }

  template <typename F>
  int findFirstImpl(int x, int l, int r, int ll, int rr, F&& func) {
    if (rr <= l || r <= ll) {
      return -1;
    }
    if (ll <= l && r <= rr && !func(a[x])) {
      return -1;
    }
    if (r - l == 1) {
      return l;
    }
    push(x, l, r);
    int m = l + (r - l) / 2;
    int res = findFirstImpl(x + 1, l, m, ll, rr, func);
    if (res == -1) {
      res = findFirstImpl(x + 2 * (m - l), m, r, ll, rr, func);
    }
    return res;
  }

  template <typename F>
  int findFirst(int ll, int rr, F&& func) {
    return findFirstImpl(0, 0, n, ll, rr, func);
  }

  template <typename F>
  int findLastImpl(int x, int l, int r, int ll, int rr, F&& func) {
    if (rr <= l || r <= ll) {
      return -1;
    }
    if (ll <= l && r <= rr && !func(a[x])) {
      return -1;
    }
    if (r - l == 1) {
      return l;
    }
    push(x, l, r);
    int m = l + (r - l) / 2;
    int res = findLastImpl(x + 2 * (m - l), m, r, ll, rr, func);
    if (res == -1) {
      res = findLastImpl(x + 1, l, m, ll, rr, func);
    }
    return res;
  }

  template <typename F>
  int findLast(int ll, int rr, F&& func) {
    return findLastImpl(0, 0, n, ll, rr, func);
  }
};