Each product undergoes the following process:

• There is a sufficient amount of that product for the next order; you can purchase \(k_i\) units.
• There is a certain amount of that product, but not enough for the next order; you can purchase between \(0\) and \(k_i\) units.
• There is zero units of that product; you can purchase \(0\) units.

The problem can be solved by managing whether we have run out of each product, while handling the second event above. Now we consider the representation on a data structure.

The problem can be solved by the following procedure:

• For \(i=1,2,\dots,Q\) in order, process the \(i\)=th order:
  • Let the preliminary answer be \(c \times k_i\), where \(c\) is the number of products among products \(l_i,l_i+1,\dots,r_i\) that have not undergo the “sold-out event” (described later).
  • Reduce the stock amount of products \(l_i,l_i+1,\dots,r_i\) by \(k_i\) each.
  • Enumerate the products with a negative amount of stock among them. For each product \(x\), perform the “sold-out event” described below:
    • If \(-s\) units of product \(x\) remain, reduce \(s\) from the answer.
    • Then, set the stock amount to a sufficiently large value so that no sold-out event will happen for product \(x\) again.
    • One can determine the existence of, and find, a product with negative stock by a binary search on a lazy segment tree.

This procedure can be implemented using a lazy segment tree.
The time complexity is \(O(N+Q \log N)\).

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using ll=long long;
const ll big=4e18;

ll op_pls(ll a,ll b){return a+b;}
ll e_pls(){return 0;}

ll op(ll a,ll b){return min(a,b);}
ll e(){return big;}
ll mapping(ll l,ll r){return l+r;}
ll composition(ll l,ll r){return l+r;}
ll id(){return 0;}

bool g(ll x){ return (x>=0); }

int main(){
  ll n;
  cin >> n;
  vector<ll> a(n);
  for(auto &nx : a){cin >> nx;}
  vector<ll> ini_pls(n,1);
  segtree<ll,op_pls,e_pls> seg_pls(ini_pls);
  lazy_segtree<ll, op, e, ll, mapping, composition, id> seg(a);

  ll q;
  cin >> q;
  while(q--){
    ll l,r,k;
    cin >> l >> r >> k;
    l--;
    ll res=seg_pls.prod(l,r)*k;
    seg.apply(l,r,-k);
    while(seg.prod(l,r)<0){
      ll pos=seg.max_right<g>(l);
      res+=seg.get(pos);
      seg.set(pos,big);
      seg_pls.set(pos,0);
    }
    cout << res << "\n";
  }
  return 0;
}