#include<bits/stdc++.h>
namespace internal {
    unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
    }
    int countr_zero(unsigned int n) {
    #ifdef _MSC_VER
        unsigned long index;
        _BitScanForward(&index, n);
        return index;
    #else
        return __builtin_ctz(n);
    #endif
    }
    constexpr int countr_zero_constexpr(unsigned int n) {
        int x = 0;
        while (!(n & (1 << x))) x++;
        return x;
    }
}
template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

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

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};
int64_t add(int64_t a,int64_t b){
  return a+b;
}
int64_t e(){
  return 0;
}
struct F{
  int64_t x;
};
int64_t mapping(F f,int64_t s){
  return f.x+s;
}
F composition(F a,F b){
  return F{a.x+b.x};
}
F id(){
  return F{(int64_t)0};
}
signed main(){ 
  uint32_t N = 8;
  std::vector<int64_t> arr = {3, 2 ,4 ,5 ,1 ,1 ,5 ,3};
  lazy_segtree<int64_t,add,e,F,mapping,composition,id> tree(arr);
  tree.apply(1,5,F{1});
  for(uint32_t i=0;i<N;i++){
    std::cout << tree.get(i) << " ";
  }
  std::cout <<"\n";
  std::cout << tree.prod(1,5) << "\n";
}

3 3 5 6 2 1 5 3
15

struct S{
    int64_t value,size,index;
};
S op(S a,S b){
    return S{a.value + b.value,a.size + b.size,a.index}; 
}
S id(){
  return S{0,0,-1};
}
struct F{
  int64_t ap,cd,index;                                                                                                                                                                       
};
S mapping(F f, S s){
  int64_t value = s.value;
  int64_t size =  s.size;
  int64_t j = s.index;
  int64_t i = f.index;
  int64_t ap = f.ap;
  int64_t cd = f.cd;
  int64_t first_term = ap + (j-i)*cd;
  int64_t sum = ((size)*(2*first_term + (size-1)*cd))/2;
  return  S{value + sum ,size,j};
}
F composition(F f,F g){
  if(f.index > g.index){
    std::swap(f,g);
  }
  int64_t Aleft = f.ap;
  int64_t Aright = g.ap;
  int64_t posLeft = f.index;
  int64_t posRight = g.index;
  int64_t cdLeft = f.cd;
  int64_t cdRight = g.cd;
  int64_t finalA = Aleft + (posRight-posLeft)*cdLeft + Aright;
  int64_t finalcd = cdLeft + cdRight;
  return F{finalA,finalcd,posRight}; 
}
F e(){
  return F{0,0,0};
}