Overview

Letting \(D_i = B_i - A_i\), the value to find is \(\sum_i \max(0, D_i)\).
Since each query is an addition or subtraction of \(D_i\) over an interval \([L,R]\), we can solve this by efficiently managing “range additions” and the “sum of positive parts”.

Analysis

First, the shortage at warehouse \(i\) is

\(\max(0, B_i - A_i)\)

Thus, if we define

\(D_i = B_i - A_i\)

the answer is

\(\sum_i \max(0, D_i)\)

The queries can be rephrased as follows:

• \(T=1\): \(B_i\) increases by \(X\)
  \(\Rightarrow D_i\) increases by \(X\)
• \(T=2\): \(A_i\) increases by \(X\)
  \(\Rightarrow D_i\) decreases by \(X\)

In other words, the problem reduces to processing the following operations:

• Add a constant value to \(D_i\) in the interval \([L,R]\)
• Output \(\sum_i \max(0,D_i)\) after each operation

A naive approach of updating all elements in the interval and recalculating the total answer on each query would take \(O(NQ)\) time, which is up to \(5 \times 10^4 \times 5 \times 10^4\) operations and will not run within the time limit.

Also, simply maintaining the “sum of positive parts” for each interval is insufficient because we cannot determine the new sum after a range addition.
For example, even if the current sum of positive parts is \(5\) in both cases:

• Adding \(-3\) to \([5, -100]\) yields a new answer of \(2\)
• Adding \(-3\) to \([2, 3]\) yields a new answer of \(0\)

Thus, we need information about the distribution of the values.

To address this, we use square root decomposition.
By keeping the elements \(D_i\) within each block sorted, we can use binary search to find “which elements become positive”.

Algorithm

We manage \(D_i = B_i - A_i\) as an array.

We divide the array into blocks of size approximately \(K\).
In this code, we set \(K=256\).

For each block, we maintain the following information:

• lazy
  The value uniformly added to the entire block
• ord
  A list of pairs of each element’s value \(v_i\) and its original position pos, sorted in ascending order of \(v_i\)
• pref
  The prefix sums of the values in ord
• ans
  The sum \(\sum \max(0,D_i)\) within the block
• idx
  The starting index where elements become positive

Here, the actual value is

\(D_i = v_i + lazy\)

Therefore, the condition for \(D_i > 0\) is

\(v_i + lazy > 0\)

which simplifies to

\(v_i > -lazy\)

Since ord is sorted in ascending order of \(v_i\), if we let idx be the first position where \(v_i > -lazy\), then the positive elements form a suffix starting from idx.

The answer for the block is

\(\sum_{k=idx}^{sz-1} (ord[k].v + lazy)\)

Using the prefix sums pref, this can be computed as:

\(\text{ans} = pref[sz] - pref[idx] + (sz - idx) \times lazy\)

For example, if the values in a block are

\([-4, -1, 2, 5]\)

and lazy = 1, the actual values are

\([-3, 0, 3, 6]\)

The positive elements correspond to \(2,5\), so the answer is

\((2+5) + 2 \times 1 = 9\)

Updating an entire block

When adding \(\delta\) to an entire block, we do not need to update each element directly.

It is sufficient to just perform:

lazy += delta

After that, we find the first position satisfying the condition \(v_i > -lazy\) using binary search and update ans.

Updating a partial block

When adding \(\delta\) to only a part of a block, we need to update the \(v_i\) values of only the corresponding elements.

Since the block size is at most \(K\), we can scan and update within the block.

However, we must maintain the sorted order of ord after the update.

In the code, this is done as follows:

1. Scan through ord.
2. Extract the elements to be updated, add \(\delta\) to their values, and place them in changed.
3. Keep the elements that are not updated as they are.
4. Merge changed and the sequence of unchanged elements to form the new ord.
5. Rebuild pref, idx, and ans.

Since the elements in changed are extracted in order from the already sorted ord and have the same \(\delta\) added to them, changed is also sorted.
Therefore, we only need to merge the two sorted sequences without resorting the entire array.

Query Processing

For each query, we first determine the value \(\delta\) to add:

• If \(T=1\), then \(\delta = X\)
• If \(T=2\), then \(\delta = -X\)

For the interval \([L,R]\), we perform:

• “Entire block addition” for blocks completely contained in the interval
• “Partial block addition” for blocks only partially overlapping at the boundaries

We maintain the overall answer total as the sum of ans of all blocks.
When a block is updated, we reflect the difference in ans before and after the update into total.

Complexity

Let \(K\) be the block size.

• Initialization: \(O(N \log K)\)
• Per query:
  • Processing partial boundary blocks: \(O(K)\)
  • Processing completely contained blocks: \(O\left(\frac{N}{K} \log K\right)\)

Therefore, overall:

• Time Complexity: \(O\left(N \log K + Q\left(K + \frac{N}{K}\log K\right)\right)\)
• Space Complexity: \(O(N)\)

In this implementation, we use \(K=256\), which is fast enough for \(N,Q \leq 5 \times 10^4\).

Implementation Points

• We only need to maintain \(D_i = B_i - A_i\); there is no need to keep track of \(A_i\) and \(B_i\) individually.

• Note that when \(T=2\), we add \(-X\) to \(D_i\).

• The answer can be up to \(10^{18}\), so we use long long.

• The input is 1-indexed, but it is converted to 0-indexed in the implementation.

• Even during partial updates, lazy is kept as is, and we only update the stored \(v_i\).
  The actual value is always considered to be \(v_i + lazy\).

• When a block’s answer changes, we update the overall answer as total += new_ans - old_ans.

  Source Code

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

using ll = long long;

class FastScanner {
    static constexpr int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char getChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

public:
    template <class T>
    bool read(T &out) {
        char c = getChar();
        if (!c) return false;

        while (c != '-' && (c < '0' || c > '9')) {
            c = getChar();
            if (!c) return false;
        }

        T sign = 1;
        if (c == '-') {
            sign = -1;
            c = getChar();
        }

        T num = 0;
        while (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            c = getChar();
        }

        out = num * sign;
        return true;
    }
};

inline void append_ll(string &s, ll x) {
    if (x == 0) {
        s.push_back('0');
        s.push_back('\n');
        return;
    }

    if (x < 0) {
        s.push_back('-');
        x = -x;
    }

    char buf[32];
    int n = 0;
    while (x > 0) {
        buf[n++] = char('0' + x % 10);
        x /= 10;
    }
    while (n--) s.push_back(buf[n]);
    s.push_back('\n');
}

struct Item {
    ll v;
    int pos;
};

struct Block {
    int l, r, sz;
    ll lazy = 0;
    ll ans = 0;
    int idx = 0;

    vector<Item> ord;
    vector<Item> tmp;
    vector<Item> changed;
    vector<ll> pref;

    void build(int L, int R, const vector<ll> &d) {
        l = L;
        r = R;
        sz = r - l + 1;
        lazy = 0;

        ord.clear();
        ord.reserve(sz);
        tmp.reserve(sz);
        changed.reserve(sz);
        pref.assign(sz + 1, 0);

        for (int i = l; i <= r; i++) {
            ord.push_back({d[i], i});
        }

        sort(ord.begin(), ord.end(), [](const Item &a, const Item &b) {
            return a.v < b.v;
        });

        rebuild_info();
    }

    void rebuild_info() {
        pref[0] = 0;
        idx = sz;
        ll th = -lazy;

        for (int i = 0; i < sz; i++) {
            if (idx == sz && ord[i].v > th) idx = i;
            pref[i + 1] = pref[i] + ord[i].v;
        }

        ans = pref[sz] - pref[idx] + (ll)(sz - idx) * lazy;
    }

    void add_all(ll delta, ll &total) {
        ll old = ans;
        lazy += delta;
        ll th = -lazy;

        if (delta > 0) {
            if (idx != 0) {
                if (ord[0].v > th) {
                    idx = 0;
                } else if (ord[idx - 1].v <= th) {
                    // unchanged
                } else {
                    int lo = 0, hi = idx;
                    while (lo < hi) {
                        int mid = (lo + hi) >> 1;
                        if (ord[mid].v <= th) lo = mid + 1;
                        else hi = mid;
                    }
                    idx = lo;
                }
            }
        } else {
            if (idx != sz) {
                if (ord[sz - 1].v <= th) {
                    idx = sz;
                } else if (ord[idx].v > th) {
                    // unchanged
                } else {
                    int lo = idx + 1, hi = sz;
                    while (lo < hi) {
                        int mid = (lo + hi) >> 1;
                        if (ord[mid].v <= th) lo = mid + 1;
                        else hi = mid;
                    }
                    idx = lo;
                }
            }
        }

        ans = pref[sz] - pref[idx] + (ll)(sz - idx) * lazy;
        total += ans - old;
    }

    void add_part(int ql, int qr, ll delta, ll &total) {
        ll old = ans;

        changed.clear();

        for (const auto &it : ord) {
            int p = it.pos;
            if (ql <= p && p <= qr) {
                changed.push_back({it.v + delta, p});
            }
        }

        tmp.clear();
        pref[0] = 0;

        int pidx = 0;
        int cidx = 0;
        int k = (int)changed.size();
        int cnt = 0;
        int newIdx = sz;
        ll th = -lazy;

        while (cnt < sz) {
            while (pidx < sz) {
                int p = ord[pidx].pos;
                if (ql <= p && p <= qr) ++pidx;
                else break;
            }

            if (cidx < k && (pidx >= sz || changed[cidx].v <= ord[pidx].v)) {
                const Item &it = changed[cidx++];
                tmp.push_back(it);
                if (newIdx == sz && it.v > th) newIdx = cnt;
                pref[cnt + 1] = pref[cnt] + it.v;
            } else {
                const Item &it = ord[pidx++];
                tmp.push_back(it);
                if (newIdx == sz && it.v > th) newIdx = cnt;
                pref[cnt + 1] = pref[cnt] + it.v;
            }

            ++cnt;
        }

        ord.swap(tmp);
        idx = newIdx;
        ans = pref[sz] - pref[idx] + (ll)(sz - idx) * lazy;
        total += ans - old;
    }
};

int main() {
    FastScanner fs;

    int N, Q;
    fs.read(N);
    fs.read(Q);

    vector<ll> d(N);
    for (int i = 0; i < N; i++) {
        ll A, B;
        fs.read(A);
        fs.read(B);
        d[i] = B - A;
    }

    static constexpr int BS = 256;
    int M = (N + BS - 1) / BS;

    vector<Block> blocks(M);
    ll total = 0;

    for (int b = 0; b < M; b++) {
        int L = b * BS;
        int R = min(N, (b + 1) * BS) - 1;
        blocks[b].build(L, R, d);
        total += blocks[b].ans;
    }

    string output;
    output.reserve((size_t)Q * 22);

    for (int qi = 0; qi < Q; qi++) {
        int T, L, R;
        ll X;
        fs.read(T);
        fs.read(L);
        fs.read(R);
        fs.read(X);

        --L;
        --R;

        ll delta = (T == 1 ? X : -X);

        int bl = L / BS;
        int br = R / BS;

        if (bl == br) {
            if (L == blocks[bl].l && R == blocks[bl].r) {
                blocks[bl].add_all(delta, total);
            } else {
                blocks[bl].add_part(L, R, delta, total);
            }
        } else {
            if (L == blocks[bl].l) {
                blocks[bl].add_all(delta, total);
            } else {
                blocks[bl].add_part(L, blocks[bl].r, delta, total);
            }

            for (int b = bl + 1; b <= br - 1; b++) {
                blocks[b].add_all(delta, total);
            }

            if (R == blocks[br].r) {
                blocks[br].add_all(delta, total);
            } else {
                blocks[br].add_part(blocks[br].l, R, delta, total);
            }
        }

        append_ll(output, total);
    }

    fwrite(output.data(), 1, output.size(), stdout);
    return 0;
}

---

This editorial was generated by gpt-5.5-high.