商品が売れていく過程を追跡すると、次の通りになります。

• 注文に対し、商品の在庫が十分ある状態である。その商品を \(k_i\) 個買える。
• 商品はあるが、在庫が足りないような注文が高々ひとつ存在する。その商品を \(0\) 個以上 \(k_i\) 個以下買える。
• 注文に対し、商品の在庫が全くない状態である。その商品を \(0\) 個買える。

在庫の有無を管理した上で、真ん中のイベントを商品ごとに管理していけば、この問題を解くことができそうです。これをデータ構造を利用して実現しましょう。

以下の手続きでこの問題を解くことができます。

• \(i=1,2,\dots,Q\) の順に、 \(i\) 件目の注文を処理する。
  • 商品 \(l_i,l_i+1,\dots,r_i\) のうち、在庫切れイベント(後述) がまだ発生していないものの個数を \(c\) とすると、暫定的に答えを \(c \times k_i\) とする。
  • 商品 \(l_i,l_i+1,\dots,r_i\) を \(k_i\) 個ずつ減らす。
  • 減らした結果この区間に在庫が負の個数である商品が存在する限り、そのような商品 \(x\) に対して以下の「在庫切れイベント」を発生させる。
    • 商品 \(x\) の在庫が \(-s\) 個である時、答えから \(s\) 減算する。
    • その後、商品 \(x\) に対して再び在庫切れイベントが発生しないよう、便宜上商品 \(x\) の在庫を十分大きく再設定する。
    • 在庫が負の個数である商品はセグメント木上の二分探索を用いて発見できる。

一連の操作は、遅延伝搬セグメント木を利用するなどの方法で実装可能です。
時間計算量は \(O(N+Q \log N)\) です。

実装例 (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;
}