Overview

This problem asks us to efficiently find the sum of the “shortages” \(\max(0, B_i - A_i)\) of each warehouse after each range addition query. We can solve this by combining Sqrt Decomposition with sorted arrays for each block.

Analysis

Simplifying the Values

Since the shortage is \(\max(0, B_i - A_i)\), if we define the difference \(D_i = B_i - A_i\), the answer we want to find can be written as:

\[\sum_{i=1}^{N} \max(0, D_i)\]

If we organize the queries as operations on \(D_i\):

• \(T_j = 1\) (increase \(B_i\) by \(X\)) \(\to\) add \(+X\) to \(D_i\) in the range \([L, R]\)
• \(T_j = 2\) (increase \(A_i\) by \(X\)) \(\to\) add \(-X\) to \(D_i\) in the range \([L, R]\)

Thus, both operations can be unified as range additions to \(D\). In other words, the problem can be rephrated as follows:

Perform range additions on an array \(D\), and after each query, output the “sum of only the positive elements \(\sum \max(0, D_i)\)”.

Limitations of a Naive Approach

If we scan all elements to calculate the sum after each range addition, it takes \(O(N)\) per query, leading to an overall complexity of \(O(NQ) = 2.5 \times 10^9\), which results in TLE.

Furthermore, due to the non-linear nature of the \(\max(0, D_i)\) operation, we cannot easily maintain “range addition + sum of positive elements” using a standard lazy segment tree (when we add a uniform value to a range, which elements become positive depends on their individual values, so we cannot update the sum using only the range sum).

Key to the Solution

If we maintain the elements of each block in a “sorted state”, we can use binary search to find the “number of elements and the sum of elements greater than a certain threshold”. When a uniform addition amount \(\mathrm{add}\) is applied to a block,

\[\sum_{i \in \text{block}} \max(0,\ D_i + \mathrm{add})\]

can be calculated by summing only the elements where \(D_i + \mathrm{add} > 0\), i.e., \(D_i > -\mathrm{add}\). Using a sorted array and prefix sums, this can be calculated in \(O(\log(\text{block size}))\).

Algorithm

We will use Sqrt Decomposition. Divide the array into blocks of size \(BS \approx \sqrt{N}\), and maintain the following for each block:

• add[b]: The lazy addition value applied to the entire block
• sorted[b]: The sorted array of \(D_i\) within the block
• prefix[b]: The prefix sums of sorted[b]
• contrib[b]: The current contribution of this block, \(\sum \max(0, D_i + \mathrm{add}[b])\)

Additionally, we maintain the sum of contributions of all blocks in total, which directly gives the answer.

Calculating Block Contribution (compContrib)

Letting the threshold be \(\mathrm{thr} = -\mathrm{add}[b]\), we can use upper_bound on sorted[b] to find the starting index pos of elements greater than \(\mathrm{thr}\). Using the number of such elements count and the sum of their original values sumvals:

\[\text{Contribution} = \text{sumvals} + \text{count} \times \mathrm{add}[b]\]

This formula works because each of these elements has \(\mathrm{add}[b]\) added to it.

Processing Range Additions

We divide the addition of delta to the range \([L, R]\) into block-wise operations as follows:

• Fully contained middle blocks: Simply do add[b] += delta. Since the sorted order does not change, we only need to recalculate the contribution (\(O(\log BS)\)).
• Partially covered boundary blocks: First, propagate add to the actual elements (pushdown), then add the values individually to the elements in the range, and finally resort the block (rebuild). \(O(BS \log BS)\).

If the query range is completely within a single block, we perform pushdown \(\to\) individual addition \(\to\) rebuild only on that block.

By updating total with the change in contribution of each modified block, we can output the answer in \(O(1)\) per query.

Complexity

Let the block size be \(BS = \sqrt{N}\) and the number of blocks be \(\sqrt{N}\).

• Per query, rebuilding at most two boundary blocks takes \(O(\sqrt{N} \log N)\), and recalculating the contributions of middle blocks takes \(O(\sqrt{N} \log N)\).
• Overall complexity is \(O(Q \sqrt{N} \log N)\).

Since \(N, Q \le 5 \times 10^4\), this is fast enough.

• Time Complexity: \(O((N + Q\sqrt{N}) \log N)\)
• Space Complexity: \(O(N)\)

Implementation Details

• Unifying by taking differences: By grouping \(T=1\) as \(+X\) and \(T=2\) as \(-X\) into delta, we can treat both operations as the same “range addition”.

• Combining lazy addition and sorted arrays: Middle blocks are fast because we only add to add without touching the actual array (D) or the sorted array. Before modifying a boundary block, we must always propagate add to D using pushdown and then rebuild the block.

• Preventing overflow: Since the output value can reach up to \(10^{18}\), we use long long (64-bit integer). \(D_i\) and all intermediate calculations should also be done in 64-bit.

• Managing contribution differences: total is the sum of contrib of all blocks. Each time we update a block, we can add the difference “(new contribution) - (old contribution)” to total to avoid summing all blocks from scratch every time.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,Q;
    scanf("%d %d",&N,&Q);
    vector<long long> D(N);
    for(int i=0;i<N;i++){
        long long a,b; scanf("%lld %lld",&a,&b);
        D[i]=b-a;
    }
    int BS = max(1, (int)sqrt((double)N));
    int nb = (N + BS - 1)/BS;
    vector<long long> add(nb,0), contrib(nb,0);
    vector<vector<long long>> sorted(nb), prefix(nb);

    auto blockStart=[&](int b){return b*BS;};
    auto blockEnd=[&](int b){return min(N,(b+1)*BS);};

    auto rebuild=[&](int b){
        int s=blockStart(b), e=blockEnd(b);
        sorted[b].assign(D.begin()+s, D.begin()+e);
        sort(sorted[b].begin(), sorted[b].end());
        int m=sorted[b].size();
        prefix[b].assign(m+1,0);
        for(int i=0;i<m;i++) prefix[b][i+1]=prefix[b][i]+sorted[b][i];
    };
    auto compContrib=[&](int b)->long long{
        long long thr = -add[b];
        auto &sv=sorted[b];
        int pos = upper_bound(sv.begin(), sv.end(), thr) - sv.begin();
        int m=sv.size();
        long long count = m - pos;
        long long sumvals = prefix[b][m] - prefix[b][pos];
        return sumvals + count * add[b];
    };

    long long total=0;
    for(int b=0;b<nb;b++){ rebuild(b); contrib[b]=compContrib(b); total+=contrib[b]; }

    auto pushdown=[&](int b){
        if(add[b]!=0){
            int s=blockStart(b), e=blockEnd(b);
            for(int i=s;i<e;i++) D[i]+=add[b];
            add[b]=0;
        }
    };

    for(int q=0;q<Q;q++){
        int T,L,R; long long X;
        scanf("%d %d %d %lld",&T,&L,&R,&X);
        L--; R--;
        long long delta = (T==1)? X : -X;
        int lb = L/BS, rb=R/BS;
        if(lb==rb){
            pushdown(lb);
            for(int i=L;i<=R;i++) D[i]+=delta;
            rebuild(lb);
            long long nc=compContrib(lb);
            total += nc - contrib[lb];
            contrib[lb]=nc;
        } else {
            pushdown(lb);
            for(int i=L; i<blockEnd(lb); i++) D[i]+=delta;
            rebuild(lb);
            long long nc=compContrib(lb);
            total += nc - contrib[lb]; contrib[lb]=nc;
            for(int b=lb+1;b<rb;b++){
                add[b]+=delta;
                long long c=compContrib(b);
                total += c - contrib[b]; contrib[b]=c;
            }
            pushdown(rb);
            for(int i=blockStart(rb); i<=R; i++) D[i]+=delta;
            rebuild(rb);
            nc=compContrib(rb);
            total += nc - contrib[rb]; contrib[rb]=nc;
        }
        printf("%lld\n", total);
    }
    return 0;
}

---

This editorial was generated by claude4.8opus-high.