概要

この問題は、各倉庫の商品数 \(A_i\) と必要見込み数 \(B_i\) に対する区間加算クエリを処理しながら、各クエリの直後に「全倉庫の不足分 \(\sum \max(0, B_i - A_i)\) の総和」を高速に求める問題です。 配列の値を差分 \(D_i = B_i - A_i\) として一元管理し、平方分割（Sqrt Decomposition）を用いることで高速にクエリを処理します。

考察

1. 差分への集約

不足分は \(\max(0, B_i - A_i)\) と定義されています。ここで \(D_i = B_i - A_i\) と定義すると、不足分は \(\max(0, D_i)\) と表せます。 - \(T_j = 1\) のとき、\(B_i\) が \(X_j\) 増えるため、\(D_i\) は \(X_j\) 増えます。 - \(T_j = 2\) のとき、\(A_i\) が \(X_j\) 増えるため、\(D_i\) は \(X_j\) 減ります。

したがって、この問題は「区間に対して値を加減算し、各クエリの後に全要素の \(\max(0, D_i)\) の総和を求める」というシンプルな問題に帰着されます。

2. 素朴なアプローチ（愚直なシミュレーション）

各クエリに対して、区間 \([L_j, R_j]\) の要素を1つずつ更新し、その後に全要素の \(\max(0, D_i)\) をループで計算すると、1クエリあたり \(O(N)\) の時間がかかります。 クエリ数が \(Q\) 個あるため、全体の計算量は \(O(QN)\) となり、今回の制約（\(N, Q \leq 5 \times 10^4\)）では実行時間制限（TLE）になってしまいます。

3. 平方分割による高速化

区間加算と、条件（\(D_i > 0\)）を満たす要素の総和を高速に行うために、平方分割（Sqrt Decomposition）を適用します。 配列をサイズ \(B \approx \sqrt{N}\) のいくつかのブロック（バケット）に分割します。

各バケットでは、以下の情報を管理します。 - lazy: バケット全体に一括で加算された値（遅延評価用） - D: バケット内の各要素の元の値 - sorted_D: バケット内の要素をソートした配列 - pref: sorted_D の累積和

バケット全体に対して値 \(v\) を加算する場合、実際の各要素を更新する代わりに lazy に \(v\) を加算するだけで済むため、\(O(1)\) で処理できます。

バケット内の \(\max(0, D_i + \text{lazy})\) の総和を求めることを考えます。 \(D_i + \text{lazy} > 0\) となる条件は \(D_i > -\text{lazy}\) です。 sorted_D はソートされているため、二分探索（std::lower_bound）を用いることで、\(D_i > -\text{lazy}\) を満たす最小のインデックス \(idx\) を \(O(\log B)\) で見つけることができます。

この \(idx\) 以降の要素（インデックス \(idx\) から \(B-1\) まで）はすべて \(D_i + \text{lazy} > 0\) を満たします。 したがって、このバケットの不足分の総和は以下のように計算できます。

\[ \sum_{i=idx}^{B-1} (D_i + \text{lazy}) = \left( \sum_{i=idx}^{B-1} D_i \right) + \text{lazy} \times (B - idx) \]

ここで、\(\displaystyle\sum_{i=idx}^{B-1} D_i\) は事前に計算しておいた累積和 pref を用いて \(O(1)\) で求められます。 これにより、1つのバケットに対するクエリを \(O(\log B)\) で処理できます。

アルゴリズム

1. 初期化:

   • \(D_i = B_i - A_i\) を計算します。
   • 配列 \(D\) をサイズ \(B \approx 220\) のバケットに分割します。
   • 各バケットについて、要素をソートした sorted_D とその累積和 pref を構築します。

2. 区間更新クエリ: 更新区間 \([L_j, R_j]\) に対して：

   • 更新区間に完全に含まれるバケットについては、lazy に加算（または減算）を行います。
   • 更新区間に一部だけ含まれるバケット（端のバケット）については：
     1. 溜まっていた lazy を各要素 D に反映させます（push）。
     2. 該当する要素 D の値を直接更新します。
     3. sorted_D と累積和 pref を再構築します（rebuild）。

3. クエリの解答:

   • すべてのバケットについて、二分探索を用いて \(D_i > -\text{lazy}\) となる範囲の和を計算し、それらを足し合わせます。

計算量

• 時間計算量: \(O(Q \sqrt{N} \log N)\)
  • バケットサイズを \(B \approx \sqrt{N}\) とします。
  • 各クエリにおいて：
    • 一部だけ含まれるバケット（最大2個）の再構築：\(O(B \log B)\)
    • 完全に含まれるバケット（最大 \(N/B\) 個）の更新：\(O(1)\)
    • 各バケット（\(N/B\) 個）での二分探索によるクエリ処理：\(O(\frac{N}{B} \log B)\)
  • \(B \approx \sqrt{N}\) のとき、1クエリあたりの計算量は \(O(\sqrt{N} \log \sqrt{N})\) となり、全体で \(O(Q \sqrt{N} \log N)\) となります。今回の制約下では十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 元の配列やバケット内の配列（ソート済みの配列、累積和）を保持するのに必要なメモリは、全体の要素数 \(N\) に比例します。

実装のポイント

• バケットサイズの決定: 理論上は \(B = \sqrt{N}\) が最適ですが、実際の実行速度は言語や定数倍の軽さに依存します。今回の実装では \(B = 220\) としており、これは \(\sqrt{50000} \approx 223\) に近い最適な値です。

• 型に注意: 不足分の総和は非常に大きくなる可能性があるため、計算途中の変数や関数の戻り値には long long 型を使用します。

• 高速な入出力: C++では ios::sync_with_stdio(false); cin.tie(nullptr); を用いて入出力を高速化することが、実行時間制限に余裕を持たせるために重要です。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Bucket {
    int L, R;
    long long lazy;
    vector<long long> D;
    vector<long long> sorted_D;
    vector<long long> pref;

    void init(int l, int r, const vector<long long>& initial_D) {
        L = l;
        R = r;
        lazy = 0;
        int sz = R - L;
        D.resize(sz);
        sorted_D.resize(sz);
        pref.resize(sz + 1);
        for (int i = 0; i < sz; ++i) {
            D[i] = initial_D[L + i];
            sorted_D[i] = D[i];
        }
        sort(sorted_D.begin(), sorted_D.end());
        pref[0] = 0;
        for (int i = 0; i < sz; ++i) {
            pref[i + 1] = pref[i] + sorted_D[i];
        }
    }

    void push() {
        if (lazy == 0) return;
        int sz = R - L;
        for (int i = 0; i < sz; ++i) {
            D[i] += lazy;
        }
        lazy = 0;
    }

    void rebuild() {
        int sz = R - L;
        for (int i = 0; i < sz; ++i) {
            sorted_D[i] = D[i];
        }
        sort(sorted_D.begin(), sorted_D.end());
        for (int i = 0; i < sz; ++i) {
            pref[i + 1] = pref[i] + sorted_D[i];
        }
    }

    void update_partial(int ql, int qr, long long val) {
        push();
        int start = max(L, ql) - L;
        int end = min(R, qr) - L;
        for (int i = start; i < end; ++i) {
            D[i] += val;
        }
        rebuild();
    }

    void update_all(long long val) {
        lazy += val;
    }

    long long query() const {
        long long target = -lazy;
        auto it = lower_bound(sorted_D.begin(), sorted_D.end(), target);
        int idx = distance(sorted_D.begin(), it);
        int sz = R - L;
        long long sum = (pref[sz] - pref[idx]) + lazy * (sz - idx);
        return sum;
    }
};

int main() {
    // Optimize input/output operations
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<long long> A(N), B(N), D(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        D[i] = B[i] - A[i];
    }

    // Set the optimal bucket size for Sqrt Decomposition
    const int bucket_size = 220;
    int num_buckets = (N + bucket_size - 1) / bucket_size;
    vector<Bucket> buckets(num_buckets);

    for (int k = 0; k < num_buckets; ++k) {
        int l = k * bucket_size;
        int r = min(N, (k + 1) * bucket_size);
        buckets[k].init(l, r, D);
    }

    for (int q = 0; q < Q; ++q) {
        int T, L, R;
        long long X;
        cin >> T >> L >> R >> X;
        int ql = L - 1;
        int qr = R;
        long long val = (T == 1) ? X : -X;

        for (int k = 0; k < num_buckets; ++k) {
            if (qr <= buckets[k].L || buckets[k].R <= ql) {
                continue;
            }
            if (ql <= buckets[k].L && buckets[k].R <= qr) {
                buckets[k].update_all(val);
            } else {
                buckets[k].update_partial(ql, qr, val);
            }
        }

        long long ans = 0;
        for (int k = 0; k < num_buckets; ++k) {
            ans += buckets[k].query();
        }
        cout << ans << "\n";
    }

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。