Overview

For \(N\) warehouses, we maintain the sum of the “shortage” of each warehouse, which is defined as \(\max(0, B_i - A_i)\). For each query, we update \(A_i\) or \(B_i\) over an interval, and output the total sum of the shortages each time.

Analysis

For each warehouse \(i\), let’s consider maintaining the value \(D_i = B_i - A_i\). In this case, the shortage of warehouse \(i\) is equal to \(\max(0, D_i)\). The changes caused by the queries can be rephrased as follows: - When \(T = 1\) (add \(X\) to \(B_i\)), add \(X\) to \(D_i\) in the interval. - When \(T = 2\) (add \(X\) to \(A_i\)), add \(-X\) to \(D_i\) in the interval.

In other words, this problem can be reduced to performing “range addition on an array” and “retrieving the sum of all positive elements” efficiently. If we scan all warehouses to calculate the sum for each query, it takes \(O(N)\) per query, resulting in \(O(NQ)\) overall, which will lead to TLE (Time Limit Exceeded). Therefore, we speed this up using square root decomposition.

Algorithm

We divide the array into buckets of size \(B\) (here, \(B \approx 800\)) to manage them. Each bucket maintains the following information: - v: The elements within the bucket (values excluding lazy propagation). - sorted_v: The sorted version of v. - sum_v: The prefix sums of sorted_v. - lazy: The lazy addition value applied to the entire bucket. - pos_sum: The sum of positive values in the bucket (elements where \(v_i + lazy > 0\)).

When a range addition query is received, we process it as follows: 1. Partially covered buckets: Directly add \(X\) to the corresponding elements in v, and rebuild the entire bucket (re-sorting and recalculating the prefix sums). Also, update the sum of positive numbers pos_sum. 2. Fully covered buckets: Simply add \(X\) to lazy. The update of the sum of positive numbers pos_sum is done quickly by performing a binary search on sorted_v. Specifically, we search for elements in sorted_v that are strictly greater than \(-lazy\), and calculate pos_sum from their count and sum.

The total sum of shortages total_sum is maintained as the sum of pos_sum across all buckets. For each query, by adding the change (delta) in each bucket’s pos_sum to total_sum, we can track the total sum in \(O(1)\) without recalculating the entire array every time.

Complexity

• Time Complexity: \(O(Q (B \log B + \frac{N}{B} \log B))\). With \(N, Q \le 5 \times 10^4\) and \(B \approx 800\), this will easily run within the time limit.
• Space Complexity: \(O(N)\)

Implementation Details

• In the update_pos_sum() function that calculates pos_sum, we use upper_bound to find the position of the first element in sorted_v that exceeds \(-lazy\). This allows us to find the count and sum of elements that will become positive in \(O(\log B)\) time.

• In the bucket reconstruction function build(), we copy the contents of v to sorted_v and sort it. Note that v does not contain the lazy value at this point (it is managed separately from lazy).

• Change the sign of the value to be added depending on the query type \(T\). When \(T = 1\), add \(+X\), and when \(T = 2\), add \(-X\).

• In the index calculation for partially covered buckets, you need to correctly compute the offset from the start of the bucket (such as L - bl * B).

  Source Code

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

This editorial was generated by or-glm5.2-high.