Overview

Let \(D_i = B_i - A_i\). The value we want to find is \(\sum_i \max(0, D_i)\).
Since each report is an operation that adds to or subtracts from \(D_i\) over an interval, we will efficiently manage “interval addition” and “sum of positive elements”.

Analysis

First, for each warehouse, what is important is not \(A_i\) and \(B_i\) themselves, but their difference:

\(D_i = B_i - A_i\)

Since the shortage is \(\max(0, D_i)\), the answer is:

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

The change caused by each report can be rephrased as follows:

• \(T_j = 1\): \(B_i\) increases by \(X_j\)
  → \(D_i\) increases by \(X_j\)
• \(T_j = 2\): \(A_i\) increases by \(X_j\)
  → \(D_i\) decreases by \(X_j\)

In other words, the problem reduces to the following:

Perform interval additions on an array \(D\), and find \(\sum \max(0, D_i)\) after each query.

Naively updating all elements in the interval for each query and then summing them up would take \(O(NQ)\) time.
Since \(N, Q \leq 5 \times 10^4\), this would require up to around \(2.5 \times 10^9\) operations, which is too slow to pass within the time limit.

Therefore, we use square root decomposition.

We divide the array into several blocks and process updates to entire blocks in bulk.
By maintaining a sorted array of elements and their prefix sums for each block, we can quickly recalculate:

\(\sum \max(0, D_i)\)

Algorithm

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

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

For each block, we maintain the following information:

• arr[i]: The value of each element
• lazy[b]: The lazy addition value applied to the entire block
• sblocks[b]: The sorted version of arr within the block
• prefs[b]: The prefix sums of sblocks[b]
• bsum[b]: The sum \(\sum \max(0, D_i)\) for this block
• total: The sum of bsum over all blocks, which is the current answer

Here, the actual value of an element is:

\(arr[i] + lazy[b]\)

Updating an Entire Block

Consider the case where we add \(\delta\) to an entire block.

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

Since this is an addition to the entire block, we do not modify arr[i] directly; instead, we add \(\delta\) to lazy[b].

After that, we calculate:

\(\sum \max(0, arr[i] + lazy[b])\)

for that block.

Let \(v\) be the sorted array of values in the block.
The condition for a value to be positive is:

\(v + lazy[b] > 0\)

which is:

\(v > -lazy[b]\)

We perform a binary search on the sorted array to find the last position where \(v \leq -lazy[b]\).
Only the elements after this position will be positive.

If the number of positive elements is \(cnt\) and the sum of their arr values is \(sum\), the total shortage for the block is:

\(sum + lazy[b] \times cnt\)

Since we maintain prefix sums, \(sum\) can be obtained in \(O(1)\) time, and the boundary position can be found in \(O(\log K)\) time using binary search.

Updating a Part of a Block

When only a part of a block is to be updated, such as at the ends of the interval, we directly update those elements.

For each element, let the actual value before the update be:

\(old = arr[i] + lazy[b]\)

and the value after the update be:

\(new = old + \delta\)

The change in the answer is:

\(\max(0, new) - \max(0, old)\)

We reflect this change in bsum[b] and total.

We also increase arr[i] by \(\delta\).

However, this operation makes the sorted array sblocks[b] in the block outdated.
Therefore, we set a dirty flag for that block.

Before using that block again in an “entire block update”, we rebuild the sorted array and prefix sums if necessary.

Query Processing

For each query on the interval \([L, R]\), we process it as follows:

1. If \(T = 1\), let \(\delta = X\); if \(T = 2\), let \(\delta = -X\).
2. Identify which blocks are covered by the interval.
3. For the partially covered blocks at the left and right ends, update the elements directly one by one.
4. For the fully covered blocks, update them in bulk using lazy addition and binary search.
5. Output total.

Complexity

Let \(K\) be the block size.

• Updating partial blocks takes \(O(K)\) time since there are at most 2 such blocks.
• There are at most \(O(N/K)\) fully covered blocks, and each takes \(O(\log K)\) time for binary search.
• Rebuilding a dirty block takes \(O(K \log K)\) time, but since this is only done when necessary for blocks that had partial updates, it can be amortized.

Therefore, the amortized time complexity per query is approximately:

\(O\left(K \log K + \frac{N}{K}\log K\right)\)

If we set \(K \approx \sqrt{N}\):

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

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

Key Implementation Points

We treat arr[i] not as the actual value itself, but as the value excluding the block’s lazy offset.
The actual value is always:

\(arr[i] + lazy[b]\)

In partial updates, instead of applying lazy before updating, we directly add \(\delta\) to arr[i].
This correctly changes the actual value by \(\delta\).

Also, since we only sum the positive parts, we use binary search to find the first position where:

\(v + lazy > 0\)

which is:

\(v > -lazy\)

Since elements that are exactly \(0\) do not contribute to the shortage, we use bisect_right.

The answer can be up to \(10^{18}\), so in other languages, you must use a 64-bit integer type. In Python, integers have arbitrary precision, so you do not need to worry about overflow.

Source Code

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N = data[0]
    Q = data[1]
    pos = 2

    arr = [0] * N
    for i in range(N):
        A = data[pos]
        B = data[pos + 1]
        pos += 2
        arr[i] = B - A

    SHIFT = 8
    BS = 1 << SHIFT
    nb = (N + BS - 1) >> SHIFT

    ends = [0] * nb
    lens = [0] * nb
    sblocks = [None] * nb
    prefs = [None] * nb
    base_sum = [0] * nb
    lazy = [0] * nb
    bsum = [0] * nb
    dirty = [0] * nb

    brgt = bisect_right
    total = 0

    for b in range(nb):
        s = b << SHIFT
        e = s + BS
        if e > N:
            e = N
        ends[b] = e
        m = e - s
        lens[b] = m

        lst = sorted(arr[s:e])
        sblocks[b] = lst

        pref = [0] * (m + 1)
        acc = 0
        j = 1
        for v in lst:
            acc += v
            pref[j] = acc
            j += 1

        prefs[b] = pref
        base_sum[b] = acc

        idx = brgt(lst, 0)
        sm = acc - pref[idx]
        bsum[b] = sm
        total += sm

    def rebuild(b, a=arr, ends=ends, lens=lens, sblocks=sblocks,
                prefs=prefs, base_sum=base_sum, dirty=dirty, shift=SHIFT):
        s = b << shift
        e = ends[b]
        m = lens[b]

        lst = sorted(a[s:e])
        sblocks[b] = lst

        pref = [0] * (m + 1)
        acc = 0
        j = 1
        for v in lst:
            acc += v
            pref[j] = acc
            j += 1

        prefs[b] = pref
        base_sum[b] = acc
        dirty[b] = 0

    def partial_update(b, left, right, delta, total,
                       a=arr, lazy=lazy, bsum=bsum, dirty=dirty):
        lz = lazy[b]
        tb = bsum[b]

        if delta > 0:
            for i in range(left, right + 1):
                base = a[i]
                old = base + lz
                a[i] = base + delta
                if old > 0:
                    tb += delta
                    total += delta
                else:
                    nv = old + delta
                    if nv > 0:
                        tb += nv
                        total += nv
        else:
            for i in range(left, right + 1):
                base = a[i]
                old = base + lz
                a[i] = base + delta
                if old > 0:
                    nv = old + delta
                    if nv > 0:
                        tb += delta
                        total += delta
                    else:
                        tb -= old
                        total -= old

        bsum[b] = tb
        dirty[b] = 1
        return total

    end_l = ends
    lazy_l = lazy
    bsum_l = bsum
    sblocks_l = sblocks
    prefs_l = prefs
    lens_l = lens
    dirty_l = dirty
    base_sum_l = base_sum
    rebuild_func = rebuild
    partial_func = partial_update

    out = []
    append = out.append

    for _ in range(Q):
        T = data[pos]
        l = data[pos + 1] - 1
        r = data[pos + 2] - 1
        X = data[pos + 3]
        pos += 4

        delta = X if T == 1 else -X

        bl = l >> SHIFT
        br = r >> SHIFT

        if bl == br:
            if l == (bl << SHIFT) and r == end_l[bl] - 1:
                fb = bl
                lb = bl
            else:
                total = partial_func(bl, l, r, delta, total)
                append(str(total))
                continue
        else:
            fb = bl
            lb = br

            if l != (bl << SHIFT):
                total = partial_func(bl, l, end_l[bl] - 1, delta, total)
                fb = bl + 1

            if r != end_l[br] - 1:
                total = partial_func(br, br << SHIFT, r, delta, total)
                lb = br - 1

        for b in range(fb, lb + 1):
            if dirty_l[b]:
                rebuild_func(b)

            old_sum = bsum_l[b]
            nlz = lazy_l[b] + delta
            lazy_l[b] = nlz

            sv = sblocks_l[b]
            m = lens_l[b]

            if sv[0] + nlz >= 0:
                new_sum = base_sum_l[b] + nlz * m
            elif sv[-1] + nlz <= 0:
                new_sum = 0
            else:
                idx = brgt(sv, -nlz)
                new_sum = base_sum_l[b] - prefs_l[b][idx] + nlz * (m - idx)

            bsum_l[b] = new_sum
            total += new_sum - old_sum

        append(str(total))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.