Overview

This problem asks us to process range addition queries on the number of items in each warehouse \(A_i\) and the expected required quantity \(B_i\), and quickly find the “total shortage of all warehouses \(\sum \max(0, B_i - A_i)\)” immediately after each query. By managing the array values uniformly as differences \(D_i = B_i - A_i\) and using Sqrt Decomposition, we can process the queries efficiently.

Analysis

1. Reducing to Differences

The shortage is defined as \(\max(0, B_i - A_i)\). If we define \(D_i = B_i - A_i\), the shortage can be represented as \(\max(0, D_i)\). - When \(T_j = 1\), \(B_i\) increases by \(X_j\), so \(D_i\) increases by \(X_j\). - When \(T_j = 2\), \(A_i\) increases by \(X_j\), so \(D_i\) decreases by \(X_j\).

Therefore, this problem reduces to a simple task: “add/subtract values on an interval, and find the sum of \(\max(0, D_i)\) over all elements after each query”.

2. Naive Approach (Brute-force Simulation)

For each query, if we update the elements in the interval \([L_j, R_j]\) one by one and then calculate \(\max(0, D_i)\) for all elements using a loop, it takes \(O(N)\) time per query. With \(Q\) queries, the overall time complexity would be \(O(QN)\), which will result in a Time Limit Exceeded (TLE) under the given constraints (\(N, Q \leq 5 \times 10^4\)).

3. Optimization using Sqrt Decomposition

To perform range additions and quickly find the sum of elements satisfying the condition (\(D_i > 0\)), we apply Sqrt Decomposition. We divide the array into several blocks (buckets) of size \(B \approx \sqrt{N}\).

In each bucket, we maintain the following information: - lazy: The value added to the entire bucket at once (for lazy propagation) - D: The original values of each element in the bucket - sorted_D: The sorted array of elements in the bucket - pref: The prefix sums of sorted_D

When adding a value \(v\) to an entire bucket, we don’t need to update each actual element. Instead, we can just add \(v\) to lazy, which can be processed in \(O(1)\) time.

Let’s consider finding the sum of \(\max(0, D_i + \text{lazy})\) within a bucket. The condition for \(D_i + \text{lazy} > 0\) is \(D_i > -\text{lazy}\). Since sorted_D is sorted, we can use binary search (std::lower_bound) to find the minimum index \(idx\) satisfying \(D_i > -\text{lazy}\) in \(O(\log B)\) time.

All elements from this \(idx\) onwards (from index \(idx\) to \(B-1\)) satisfy \(D_i + \text{lazy} > 0\). Therefore, the sum of the shortages in this bucket can be calculated as follows:

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

Here, \(\displaystyle\sum_{i=idx}^{B-1} D_i\) can be obtained in \(O(1)\) time using the precomputed prefix sums pref. This allows us to process the query for a single bucket in \(O(\log B)\) time.

Algorithm

1. Initialization:

   • Calculate \(D_i = B_i - A_i\).
   • Divide the array \(D\) into buckets of size \(B \approx 220\).
   • For each bucket, construct the sorted array sorted_D and its prefix sums pref.

2. Range Update Query: For the update interval \([L_j, R_j]\):

   • For buckets fully contained in the update interval, add (or subtract) the value to/from lazy.
   • For buckets only partially contained in the update interval (the boundary buckets):
     1. Propagate the accumulated lazy value to each element D (push).
     2. Directly update the values of the corresponding elements in D.
     3. Reconstruct sorted_D and the prefix sums pref (rebuild).

3. Answering Queries:

   • For all buckets, use binary search to calculate the sum of the elements satisfying \(D_i > -\text{lazy}\), and sum them up.

Complexity

• Time Complexity: \(O(Q \sqrt{N} \log N)\)
  • Let the bucket size be \(B \approx \sqrt{N}\).
  • In each query:
    • Reconstructing partially contained buckets (at most 2): \(O(B \log B)\)
    • Updating fully contained buckets (at most \(N/B\) buckets): \(O(1)\)
    • Query processing using binary search in each bucket (\(N/B\) buckets): \(O(\frac{N}{B} \log B)\)
  • When \(B \approx \sqrt{N}\), the complexity per query is \(O(\sqrt{N} \log \sqrt{N})\), resulting in an overall time complexity of \(O(Q \sqrt{N} \log N)\). This is fast enough to run within the time limit under the given constraints.
• Space Complexity: \(O(N)\)
  • The memory required to store the original array and the bucket arrays (sorted arrays, prefix sums) is proportional to the total number of elements \(N\).

Implementation Points

• Determining the Bucket Size: Theoretically, \(B = \sqrt{N}\) is optimal, but the actual execution speed depends on the language and constant factor optimizations. In this implementation, we set \(B = 220\), which is close to the optimal value of \(\sqrt{50000} \approx 223\).

• Be Careful with Data Types: Since the sum of the shortages can be very large, use long long (or 64-bit integer types) for intermediate variables and function return values.

• Fast I/O: In C++, using ios::sync_with_stdio(false); cin.tie(nullptr); to speed up input/output is important to ensure a comfortable margin within the time limit.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-high.