概要

各倉庫について「必要見込み数 \(B_i\)」と「現在の商品数 \(A_i\)」の差分を管理し、区間に対する \(B_i\) や \(A_i\) の加算（区間加算）を繰り返しながら、毎回「全倉庫の不足分の合計 \(\sum \max(0, B_i - A_i)\)」を求める問題です。

考察

差分でまとめて考える

倉庫 \(i\) の不足分は \(\max(0,\ B_i - A_i)\) です。そこで各倉庫について

\[C_i = B_i - A_i\]

という値を考えると、求めたいのは \(\displaystyle\sum_{i=1}^N \max(0,\ C_i)\) になります。

このとき、各操作は次のように \(C_i\) への区間加算に統一できます。

• \(T_j = 1\)（\(B_i\) を \(X_j\) 増やす）: 区間 \([L_j, R_j]\) の \(C_i\) に \(+X_j\)
• \(T_j = 2\)（\(A_i\) を \(X_j\) 増やす）: 区間 \([L_j, R_j]\) の \(C_i\) に \(-X_j\)

つまり「区間加算」を行いながら、「全要素の正の部分の総和 \(\sum \max(0, C_i)\)」を毎回求めればよい、という問題に帰着します。

素朴な方法では間に合わない

毎回の操作後に全 \(N\) 個を見て合計を計算すると、1 回あたり \(O(N)\)、全体で \(O(NQ) = 5\times10^4 \times 5\times10^4 = 2.5\times10^9\) となり、TLE します。

難しいのは \(\max(0, C_i)\) の総和という「区切りのある」量を扱う点です。単純な区間加算・区間和なら BIT などで楽ですが、各要素ごとに \(0\) との比較が入るため、加算によって「不足している倉庫」と「足りている倉庫」の境目が変わってしまい、通常の遅延セグメント木では一括処理しづらいのです。

解決のアイデア（平方分割 + ソート）

ここで 平方分割（ブロック分割） が有効です。配列を大きさ約 \(\sqrt{N}\) のブロックに分け、各ブロック内の値をソートして保持します。

ブロックに加算遅延値 \(Lz\) が乗っている状態で、そのブロックの正の部分の総和は

\[\sum_{i \in \text{block}} \max(0,\ v_i + Lz)\]

です。ブロック内がソート済みなら、\(v_i + Lz > 0 \iff v_i > -Lz\) なので、\(-Lz\) を二分探索すれば「正に寄与する要素の範囲」がすぐ分かります。あとは

\[(\text{その範囲の値の和}) + (\text{その範囲の要素数}) \times Lz\]

で寄与が求まります（要素の和は事前計算した累積和で \(O(1)\)）。これにより、ブロック全体に加算する操作は二分探索 \(O(\log \sqrt N)\) で寄与を更新できます。

アルゴリズム

各ブロックについて以下を管理します。

• blk_vals: ブロック内の値（\(C_i\)）をソートした配列
• blk_pre: そのソート済み配列の累積和
• blk_lazy: ブロック全体への加算遅延値 \(Lz\)
• blk_contrib: そのブロックが答えに寄与している量 \(\sum \max(0, v_i + Lz)\)

全体の答え total は全ブロックの blk_contrib の和です。

区間 \([l, r]\) に \(\delta\) を加算する処理は、平方分割の定石通り 2 種類に分けます。

1. ブロックにまたがらない・端の部分ブロック（apply_partial）

ブロックの一部だけが対象になる場合は、まず溜まっている遅延 \(Lz\) を実際の値に反映してから、対象範囲の要素に \(\delta\) を直接加算し、そのブロックを再ソート＆累積和を再計算します。その上で二分探索により寄与を求め直します。これは 1 ブロックあたり \(O(\sqrt N \log \sqrt N)\) です。

2. 完全に含まれる中間ブロック

ブロック全体が対象範囲に含まれる場合は、ソート配列をいじらず blk_lazy に \(\delta\) を加算するだけにします。寄与は「考察」で述べたように、二分探索で \(-Lz\) の位置を求め、累積和を使って \(O(\log \sqrt N)\) で更新します。

これにより 1 操作あたり、端の最大 2 ブロックの再構築 \(O(\sqrt N \log \sqrt N)\) と、中間の最大 \(\sqrt N\) 個のブロックの遅延更新 \(O(\sqrt N \log \sqrt N)\) で処理できます。

計算量

ブロックサイズを \(B \approx \sqrt N\)、ブロック数を \(\approx \sqrt N\) とします。

• 1 操作あたり：端ブロックの再構築が \(O(\sqrt N \log N)\)、中間ブロックの遅延更新が \(O(\sqrt N \log N)\)

• 全体：

• 時間計算量: \(O\bigl((N + Q\sqrt N)\log N\bigr)\)

• 空間計算量: \(O(N)\)（各値とその累積和、ブロック管理情報）

\(N, Q \le 5\times10^4\) なので \(Q\sqrt N \approx 5\times10^4 \times 224 \approx 1.1\times10^7\) 程度であり、十分高速に動作します。

実装のポイント

• \(C_i = B_i - A_i\) の差分配列に統一することで、2 種類の操作を符号付きの区間加算（\(T=1\) なら \(+X\)、\(T=2\) なら \(-X\)）に一本化できます。これが見通しを良くする鍵です。

• 中間ブロックではソート配列を絶対に作り直さないこと。遅延値 \(Lz\) だけ更新し、寄与は二分探索＋累積和で計算します。ここで毎回再ソートしてしまうと計算量が悪化します。

• 部分ブロックを更新する際は、先に溜まっている遅延 \(Lz\) を実値に反映してから \(\delta\) を加え、その後で再ソートする必要があります。順序を間違えると値がずれます。

• 寄与の計算式 (pre[-1] - pre[i0]) + cnt * Lz は、「\(-Lz\) より大きい要素の値の総和」に「それらの個数 × \(Lz\)」を足したもので、ちょうど \(\sum \max(0, v_i + Lz)\) になっています。

• 答えは最大 \(10^{18}\) 程度になり得ますが、Python では多倍長整数なのでオーバーフローの心配はありません。

  ソースコード

import sys
import bisect

def main():
    data = sys.stdin.buffer.read().split()
    pos = 0
    N = int(data[pos]); pos += 1
    Q = int(data[pos]); pos += 1

    base = [0] * N
    for i in range(N):
        a = int(data[pos]); b = int(data[pos + 1]); pos += 2
        base[i] = b - a

    bs = max(1, int(N ** 0.5))
    nb = (N + bs - 1) // bs

    blk_vals = []
    blk_pre = []
    blk_lazy = [0] * nb
    blk_contrib = [0] * nb

    for k in range(nb):
        s = k * bs
        e = N if s + bs > N else s + bs
        v = sorted(base[s:e])
        pre = [0] * (len(v) + 1)
        acc = 0
        for t in range(len(v)):
            acc += v[t]
            pre[t + 1] = acc
        blk_vals.append(v)
        blk_pre.append(pre)

    total = 0
    bisect_right = bisect.bisect_right
    for k in range(nb):
        v = blk_vals[k]
        pre = blk_pre[k]
        i0 = bisect_right(v, 0)
        c = pre[-1] - pre[i0]
        blk_contrib[k] = c
        total += c

    out = []

    def apply_partial(k, lo, hi, delta):
        nonlocal total
        s = k * bs
        e = N if s + bs > N else s + bs
        L = blk_lazy[k]
        if L:
            for i in range(s, e):
                base[i] += L
            blk_lazy[k] = 0
        if delta:
            for i in range(lo, hi + 1):
                base[i] += delta
        v = sorted(base[s:e])
        pre = [0] * (len(v) + 1)
        acc = 0
        for t in range(len(v)):
            acc += v[t]
            pre[t + 1] = acc
        blk_vals[k] = v
        blk_pre[k] = pre
        i0 = bisect_right(v, 0)
        newc = pre[-1] - pre[i0]
        total += newc - blk_contrib[k]
        blk_contrib[k] = newc

    for _ in range(Q):
        T = int(data[pos]); L = int(data[pos + 1]); R = int(data[pos + 2]); X = int(data[pos + 3])
        pos += 4
        delta = X if T == 1 else -X
        l = L - 1
        r = R - 1
        bl = l // bs
        br = r // bs
        if bl == br:
            apply_partial(bl, l, r, delta)
        else:
            apply_partial(bl, l, (bl + 1) * bs - 1, delta)
            apply_partial(br, br * bs, r, delta)
            for k in range(bl + 1, br):
                blk_lazy[k] += delta
                Lz = blk_lazy[k]
                v = blk_vals[k]
                pre = blk_pre[k]
                i0 = bisect_right(v, -Lz)
                cnt = len(v) - i0
                newc = (pre[-1] - pre[i0]) + cnt * Lz
                total += newc - blk_contrib[k]
                blk_contrib[k] = newc
        out.append(str(total))

    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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