\(A_i := B_i-A_i\) と置きなおすことで、変数を \(1\) つで済ませるとします。

平方分割 を利用します。
配列 \(A\) をサイズ \(S\) ごとに分割してひとつのブロックであるとみなします。
各ブロックにて、以下の情報を保存します。

• ブロック内の値を降順ソートしたもの
• 上の累積和
• ブロック内の各要素と \(0\) との小さくない方の総和
• ブロック全体に対する、遅延された加算の値 \(lazy\)

\([L,R]\) に対する \(X\) の加算は以下のように処理します。

• \([L,R]\) に完全に含まれているブロックについては、以下の処理を行う。

  • \(lazy\) に \(X\) 加算する。
    • 実際の各要素の値は \(A_i+lazy\) となることに注意されたい。
  • その結果 \(A_i+lazy\) と \(0\) とを比較して前者の方が大きくなる領域の大きさが変化しうる。
    • この領域の大きさを二分探索する。
    • ブロック内の値を降順ソートしたもの、およびその累積和を保持しているため、更新を \(O(\log S)\) 時間で行うことができる。

• \([L,R]\) に一部のみ含まれているブロックについては、以下の処理を行う。

  • \(lazy\) をブロック内全ての要素に加算する。
  • その後、 \([L,R]\) に絡む要素のみ \(X\) 加算する。
  • その後、ブロックに関する全ての情報を再計算する。
  • 全ての情報を再計算するとき、時間計算量 \(O(S \log S)\) を要する。ただし、このケースは一度の区間加算について高々 \(2\) 回しか発生しません。

初期化は \(O(N \log S)\) で、 \(Q\) 個のクエリの処理は \(O(Q(\frac{N}{S} + S) \log S)\) 時間で完了します。
\(S\) を適切に決定することで、実行時間制限に間に合わせることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll BSIZE=100;

vector<ll> v;

ll res=0;
vector<vector<ll>> block;
vector<vector<ll>> bsum;
vector<ll> bres;
vector<ll> lazy;

void prop(ll x){
  for(ll i=x*BSIZE;i<(x+1)*BSIZE;i++){
    v[i]+=lazy[x];
  }
  lazy[x]=0;
}

void slide(ll i,ll x){
  res-=bres[i];
  lazy[i]+=x;
  auto it=lower_bound(block[i].begin(),block[i].end(),-lazy[i],greater<ll>());
  ll cnt=(it-block[i].begin());
  if(cnt==0){bres[i]=0;}
  else{
    bres[i]=bsum[i][cnt-1]+lazy[i]*cnt;
  }
  res+=bres[i];
}

void rebuild(ll i){
  res-=bres[i];
  block[i].clear();
  bres[i]=0;
  for(ll j=0;j<BSIZE;j++){
    ll pos=i*BSIZE+j;
    block[i].push_back(v[pos]);
    bres[i]+=max(0ll,v[pos]);
  }
  sort(block[i].rbegin(),block[i].rend());
  bsum[i]=block[i];
  for(ll j=1;j<BSIZE;j++){
    bsum[i][j]+=bsum[i][j-1];
  }
  res+=bres[i];
}

int main(){
  ll N,Q;
  cin >> N >> Q;
  for(ll i=0;i<N;i++){
    ll A,B;
    cin >> A >> B;
    v.push_back(B-A);
  }
  while(v.size()%BSIZE!=0){v.push_back(0);}

  ll bnum=v.size()/BSIZE;
  block.resize(bnum);
  bsum.resize(bnum);
  bres.resize(bnum);
  lazy.resize(bnum);
  for(ll i=0;i<bnum;i++){
    bres[i]=0;
    rebuild(i);
    lazy[i]=0;
  }

  while(Q--){
    ll T,L,R,X;
    cin >> T >> L >> R >> X;
    L--; R--;
    if(T==2){X*=-1;}
    ll lb=L/BSIZE;
    ll rb=R/BSIZE;
    if(lb==rb){
      prop(lb);
      for(ll i=L;i<=R;i++){
        v[i]+=X;
      }
      rebuild(lb);
    }
    else{
      prop(lb);
      prop(rb);
      for(ll i=L;i<(lb+1)*BSIZE;i++){
        v[i]+=X;
      }
      for(ll i=lb+1;i<rb;i++){
        slide(i,X);
      }
      for(ll i=rb*BSIZE;i<=R;i++){
        v[i]+=X;
      }
      rebuild(lb);
      rebuild(rb);
    }
    cout << res << "\n";
  }
  return 0;
}