概要

各倉庫の「不足分」\(\max(0, B_i - A_i)\) の総和を、区間加算のたびに高速に求める問題です。平方分割（Sqrt Decomposition）と各ブロックのソート済み配列を組み合わせて解きます。

考察

値をまとめる

不足分は \(\max(0, B_i - A_i)\) なので、差 \(D_i = B_i - A_i\) を考えると、求める答えは

\[\sum_{i=1}^{N} \max(0, D_i)\]

と書けます。

クエリを \(D_i\) への操作として整理すると、

• \(T_j = 1\)（\(B_i\) を \(X\) 増やす）→ 区間 \([L, R]\) の \(D_i\) を \(+X\)
• \(T_j = 2\)（\(A_i\) を \(X\) 増やす）→ 区間 \([L, R]\) の \(D_i\) を \(-X\)

となり、どちらも \(D\) への区間加算に統一できます。つまり問題は次のように言い換えられます。

配列 \(D\) に対し区間加算を行い、毎回「正の部分だけの総和 \(\sum \max(0, D_i)\)」を出力せよ。

素朴なアプローチの問題点

区間加算のたびに全要素を走査して総和を計算すると、1 クエリあたり \(O(N)\) かかり、全体で \(O(NQ) = 2.5 \times 10^9\) となって TLE します。

また、\(\max(0, D_i)\) という非線形な操作のため、通常の遅延セグメント木で「区間加算 + 正の部分の和」を単純に管理することはできません（区間に一律の値を足したとき、どの要素が正になるかが要素の値に依存するため、区間の和だけでは更新できない）。

解決の鍵

ブロックごとに「値がソートされた状態」を保持しておけば、「ある閾値より大きい要素の個数と総和」を二分探索で求められます。ブロックに一律の加算量 \(\mathrm{add}\) が乗っているとき、

\[\sum_{i \in \text{block}} \max(0,\ D_i + \mathrm{add})\]

は、\(D_i + \mathrm{add} > 0\)、すなわち \(D_i > -\mathrm{add}\) となる要素だけを足せばよく、ソート済み配列＋累積和を使えば \(O(\log(\text{ブロックサイズ}))\) で計算できます。

アルゴリズム

平方分割を用います。配列をサイズ \(BS \approx \sqrt{N}\) のブロックに分割し、各ブロックについて以下を持ちます。

• add[b]：ブロック全体への遅延加算量（lazy）
• sorted[b]：ブロック内の \(D_i\) をソートした配列
• prefix[b]：sorted[b] の累積和
• contrib[b]：このブロックの現在の寄与 \(\sum \max(0, D_i + \mathrm{add}[b])\)

そして全ブロックの寄与の合計 total を持ち、これがそのまま答えになります。

ブロックの寄与計算（compContrib）

閾値 \(\mathrm{thr} = -\mathrm{add}[b]\) として、sorted[b] 上で upper_bound により \(\mathrm{thr}\) より大きい要素の開始位置 pos を求めます。それらの要素数 count と元の値の総和 sumvals を使い、

\[\text{寄与} = \text{sumvals} + \text{count} \times \mathrm{add}[b]\]

で求まります（各要素に \(\mathrm{add}[b]\) が乗るため）。

区間加算の処理

区間 \([L, R]\) への加算 delta を、ブロック単位で次のように分けます。

• 完全に含まれる中間ブロック：add[b] += delta とするだけ。ソート順は変わらないので、寄与を再計算するだけで済む（\(O(\log BS)\)）。
• 端の半端なブロック：一旦 add を実体に反映（pushdown）してから個別に値を足し、ソートし直す（rebuild）。\(O(BS \log BS)\)。

クエリが 1 つのブロック内で完結する場合は、そのブロックだけ pushdown → 個別加算 → rebuild します。

各ブロックの寄与の変化分を total に反映していくことで、毎クエリ \(O(1)\) で答えを出力できます。

計算量

ブロックサイズを \(BS = \sqrt{N}\)、ブロック数を \(\sqrt{N}\) とします。

• 1 クエリあたり、端の最大 2 ブロックの再構築に \(O(\sqrt{N} \log N)\)、中間ブロックの寄与再計算に \(O(\sqrt{N} \log N)\)
• 全体で \(O(Q \sqrt{N} \log N)\)

\(N, Q \le 5 \times 10^4\) なので十分高速です。

• 時間計算量: \(O((N + Q\sqrt{N}) \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 差を取って統一：\(T=1\) は \(+X\)、\(T=2\) は \(-X\) として delta にまとめると、両方を同じ「区間加算」として扱えます。

• 遅延加算とソート配列の両立：中間ブロックは add を足すだけで実体（D）やソート配列を触らないため高速です。端のブロックを操作する前には必ず pushdown で add を D に反映させてから rebuild する必要があります。

• オーバーフロー対策：出力値は最大 \(10^{18}\) に達するため、long long（64bit 整数）を使います。\(D_i\) や中間計算もすべて 64bit で行います。

• 寄与の差分管理：total は各ブロックの contrib の合計です。ブロックを更新するたびに「新しい寄与 − 古い寄与」を total に加えることで、毎回全ブロックを足し直さずに済みます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,Q;
    scanf("%d %d",&N,&Q);
    vector<long long> D(N);
    for(int i=0;i<N;i++){
        long long a,b; scanf("%lld %lld",&a,&b);
        D[i]=b-a;
    }
    int BS = max(1, (int)sqrt((double)N));
    int nb = (N + BS - 1)/BS;
    vector<long long> add(nb,0), contrib(nb,0);
    vector<vector<long long>> sorted(nb), prefix(nb);

    auto blockStart=[&](int b){return b*BS;};
    auto blockEnd=[&](int b){return min(N,(b+1)*BS);};

    auto rebuild=[&](int b){
        int s=blockStart(b), e=blockEnd(b);
        sorted[b].assign(D.begin()+s, D.begin()+e);
        sort(sorted[b].begin(), sorted[b].end());
        int m=sorted[b].size();
        prefix[b].assign(m+1,0);
        for(int i=0;i<m;i++) prefix[b][i+1]=prefix[b][i]+sorted[b][i];
    };
    auto compContrib=[&](int b)->long long{
        long long thr = -add[b];
        auto &sv=sorted[b];
        int pos = upper_bound(sv.begin(), sv.end(), thr) - sv.begin();
        int m=sv.size();
        long long count = m - pos;
        long long sumvals = prefix[b][m] - prefix[b][pos];
        return sumvals + count * add[b];
    };

    long long total=0;
    for(int b=0;b<nb;b++){ rebuild(b); contrib[b]=compContrib(b); total+=contrib[b]; }

    auto pushdown=[&](int b){
        if(add[b]!=0){
            int s=blockStart(b), e=blockEnd(b);
            for(int i=s;i<e;i++) D[i]+=add[b];
            add[b]=0;
        }
    };

    for(int q=0;q<Q;q++){
        int T,L,R; long long X;
        scanf("%d %d %d %lld",&T,&L,&R,&X);
        L--; R--;
        long long delta = (T==1)? X : -X;
        int lb = L/BS, rb=R/BS;
        if(lb==rb){
            pushdown(lb);
            for(int i=L;i<=R;i++) D[i]+=delta;
            rebuild(lb);
            long long nc=compContrib(lb);
            total += nc - contrib[lb];
            contrib[lb]=nc;
        } else {
            pushdown(lb);
            for(int i=L; i<blockEnd(lb); i++) D[i]+=delta;
            rebuild(lb);
            long long nc=compContrib(lb);
            total += nc - contrib[lb]; contrib[lb]=nc;
            for(int b=lb+1;b<rb;b++){
                add[b]+=delta;
                long long c=compContrib(b);
                total += c - contrib[b]; contrib[b]=c;
            }
            pushdown(rb);
            for(int i=blockStart(rb); i<=R; i++) D[i]+=delta;
            rebuild(rb);
            nc=compContrib(rb);
            total += nc - contrib[rb]; contrib[rb]=nc;
        }
        printf("%lld\n", total);
    }
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。