概要

\(N\) 個の倉庫について、各倉庫の「不足分」である \(\max(0, B_i - A_i)\) の合計を管理します。クエリごとに区間の \(A_i\) または \(B_i\) を更新し、その都度全体の不足分の合計を出力する問題です。

考察

各倉庫 \(i\) について、\(D_i = B_i - A_i\) という値を管理することを考えます。 このとき、倉庫 \(i\) の不足分は \(\max(0, D_i)\) と等しくなります。 クエリによる変化は以下のように置き換えられます。 - \(T = 1\)（\(B_i\) に \(X\) を加算）のとき、区間の \(D_i\) に \(X\) を加算する。 - \(T = 2\)（\(A_i\) に \(X\) を加算）のとき、区間の \(D_i\) に \(-X\) を加算する。

つまり、この問題は「配列の区間に対する加算」と「全要素の正の数の和の取得」を高速に行う問題に帰着できます。 毎回全ての倉庫を走査して和を計算すると、1クエリあたり \(O(N)\) かかり \(O(NQ)\) となりTLEしてしまいます。そこで、平方分割（バケット分割）を用いて高速化します。

アルゴリズム

配列をサイズ \(B\)（ここでは \(B \approx 800\)）のバケットに分割して管理します。各バケットには以下の情報を保持します。 - v: バケット内の要素（遅延評価を含まない値） - sorted_v: v をソートした配列 - sum_v: sorted_v の累積和 - lazy: バケット全体への加算値 - pos_sum: バケット内の正の値（\(v_i + lazy > 0\) となる要素）の和

区間加算クエリが来たとき、以下のように処理します。 1. 部分的に含まれるバケット: v の該当要素に直接 \(X\) を加算し、バケット全体を再構築（ソートと累積和の再計算）します。正の数の和 pos_sum も更新します。 2. 完全に含まれるバケット: lazy に \(X\) を足すだけで済ませます。正の数の和 pos_sum の更新は、sorted_v に対して二分探索を行うことで高速に行います。具体的には、sorted_v の要素のうち \(-lazy\) より大きいものを探し、その個数と和から pos_sum を計算します。

全体の不足分の合計 total_sum は、各バケットの pos_sum の総和として管理します。クエリ処理ごとに、各バケットの pos_sum の増減分（デルタ）を total_sum に加算していくことで、毎回全体を計算し直すことなく \(O(1)\) で合計値を追跡できます。

計算量

• 時間計算量: \(O(Q (B \log B + \frac{N}{B} \log B))\)。\(N, Q \le 5 \times 10^4\) で \(B = 800\) 程度とすれば十分に間に合います。
• 空間計算量: \(O(N)\)

実装のポイント

• pos_sum を計算する update_pos_sum() 関数では、upper_bound を用いて sorted_v の中で \(-lazy\) を超える最初の要素の位置を見つけます。これにより、正の値になる要素の個数と和を \(O(\log B)\) で求めることができます。

• バケットの再構築 build() では、v の内容を sorted_v にコピーしてソートします。このとき v には lazy の値は含まれていない（lazy とは別で管理している）ことに注意してください。

• クエリの \(T\) に応じて加算する値の符号を変えます。\(T = 1\) のときは \(+X\)、\(T = 2\) のときは \(-X\) です。

• 部分的に含まれるバケットのインデックス計算では、バケットの先頭からのオフセット（L - bl * B など）を正しく計算する必要があります。

  ソースコード

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

using namespace std;

struct Bucket {
    vector<long long> v;
    vector<long long> sorted_v;
    vector<long long> sum_v;
    long long lazy = 0;
    long long pos_sum = 0;

    void build() {
        sorted_v = v;
        sort(sorted_v.begin(), sorted_v.end());
        sum_v.assign(sorted_v.size() + 1, 0);
        for (size_t i = 0; i < sorted_v.size(); ++i) {
            sum_v[i+1] = sum_v[i] + sorted_v[i];
        }
        update_pos_sum();
    }

    void update_pos_sum() {
        auto it = upper_bound(sorted_v.begin(), sorted_v.end(), -lazy);
        int idx = it - sorted_v.begin();
        long long cnt = sorted_v.size() - idx;
        long long sum = sum_v.back() - sum_v[idx];
        pos_sum = sum + cnt * lazy;
    }

    long long add_all(long long X) {
        long long old_pos_sum = pos_sum;
        lazy += X;
        update_pos_sum();
        return pos_sum - old_pos_sum;
    }

    long long add_part(int L, int R, long long X) {
        for (int i = L; i <= R; ++i) {
            v[i] += X;
        }
        long long old_pos_sum = pos_sum;
        build();
        return pos_sum - old_pos_sum;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    
    int B = 800;
    int num_buckets = (N + B - 1) / B;
    vector<Bucket> buckets(num_buckets);
    
    for (int i = 0; i < N; ++i) {
        long long a, b;
        cin >> a >> b;
        buckets[i / B].v.push_back(b - a);
    }
    
    long long total_sum = 0;
    for (int i = 0; i < num_buckets; ++i) {
        buckets[i].build();
        total_sum += buckets[i].pos_sum;
    }
    
    for (int j = 0; j < Q; ++j) {
        int T, L, R;
        long long X;
        cin >> T >> L >> R >> X;
        L--; R--;
        
        long long delta = (T == 1) ? X : -X;
        int bl = L / B;
        int br = R / B;
        
        if (bl == br) {
            total_sum += buckets[bl].add_part(L - bl * B, R - bl * B, delta);
        } else {
            total_sum += buckets[bl].add_part(L - bl * B, buckets[bl].v.size() - 1, delta);
            total_sum += buckets[br].add_part(0, R - br * B, delta);
            for (int i = bl + 1; i < br; ++i) {
                total_sum += buckets[i].add_all(delta);
            }
        }
        
        cout << total_sum << "\n";
    }
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。