Overview

For each warehouse, we maintain the difference between the “expected required number \(B_i\)” and the “current number of products \(A_i\)”. While repeatedly performing interval additions to \(B_i\) or \(A_i\), we need to find the “total shortage across all warehouses \(\sum \max(0, B_i - A_i)\)” at each step.

Analysis

Thinking in terms of differences

The shortage of warehouse \(i\) is \(\max(0,\ B_i - A_i)\). Thus, if we consider the value

\[C_i = B_i - A_i\]

for each warehouse, what we want to find is \(\displaystyle\sum_{i=1}^N \max(0,\ C_i)\).

At this point, each operation can be unified as an interval addition to \(C_i\) as follows:

• \(T_j = 1\) (increase \(B_i\) by \(X_j\)): Add \(+X_j\) to \(C_i\) in the interval \([L_j, R_j]\)
• \(T_j = 2\) (increase \(A_i\) by \(X_j\)): Add \(-X_j\) to \(C_i\) in the interval \([L_j, R_j]\)

In other words, the problem reduces to performing “interval additions” while finding the “sum of positive parts of all elements \(\sum \max(0, C_i)\)” after each operation.

Naive approach is too slow

If we calculate the sum by inspecting all \(N\) elements after each operation, it takes \(O(N)\) per operation, and \(O(NQ) = 5\times10^4 \times 5\times10^4 = 2.5\times10^9\) in total, resulting in a TLE (Time Limit Exceeded).

The difficulty lies in handling the “bounded” quantity, which is the sum of \(\max(0, C_i)\). While simple interval additions and interval sums can be easily handled with a BIT (Binary Indexed Tree) or similar, the comparison with \(0\) for each element means that addition changes the boundary between “shortage warehouses” and “sufficient warehouses”. This makes it hard to process collectively using a standard lazy segment tree.

Idea for Solution (Square Root Decomposition + Sorting)

Here, Square Root Decomposition (block decomposition) is effective. We divide the array into blocks of size approximately \(\sqrt{N}\) and keep the values within each block sorted.

With a lazy addition value \(Lz\) applied to a block, the sum of the positive parts in that block is:

\[\sum_{i \in \text{block}} \max(0,\ v_i + Lz)\]

If the block is sorted, then \(v_i + Lz > 0 \iff v_i > -Lz\). Thus, by performing a binary search for \(-Lz\), we can quickly find the “range of elements contributing positively”. Then, the contribution can be found as:

\[(\text{sum of values in that range}) + (\text{number of elements in that range}) \times Lz\]

(The sum of elements can be obtained in \(O(1)\) using a precalculated prefix sum). With this, an operation that adds to the entire block can update its contribution in \(O(\log \sqrt N)\) using binary search.

Algorithm

We maintain the following for each block:

• blk_vals: Sorted array of values (\(C_i\)) within the block
• blk_pre: Prefix sums of the sorted array
• blk_lazy: Lazy addition value \(Lz\) for the entire block
• blk_contrib: The amount this block contributes to the answer, \(\sum \max(0, v_i + Lz)\)

The overall answer total is the sum of blk_contrib of all blocks.

The process of adding \(\delta\) to the interval \([l, r]\) is divided into two cases, following the standard approach of square root decomposition.

1. Partial blocks at the ends / intervals not spanning multiple blocks (apply_partial)

When only a part of a block is affected, we first apply the accumulated lazy value \(Lz\) to the actual elements, directly add \(\delta\) to the elements in the target range, and then re-sort the block and recalculate its prefix sums. After that, we re-evaluate the contribution using binary search. This takes \(O(\sqrt N \log \sqrt N)\) per block.

2. Fully contained intermediate blocks

When the entire block is contained in the target range, we do not touch the sorted array and simply add \(\delta\) to blk_lazy. As described in the “Analysis” section, the contribution is updated in \(O(\log \sqrt N)\) by finding the position of \(-Lz\) with binary search and using the prefix sums.

Consequently, each operation can be processed with at most 2 end-block reconstructions taking \(O(\sqrt N \log \sqrt N)\) and at most \(\sqrt N\) intermediate block lazy updates taking \(O(\sqrt N \log \sqrt N)\).

Complexity

Let the block size be \(B \approx \sqrt N\), and the number of blocks be \(\approx \sqrt N\).

• Per operation: End-block reconstruction takes \(O(\sqrt N \log N)\), and intermediate block lazy updates take \(O(\sqrt N \log N)\).
• Overall:
  • Time Complexity: \(O\bigl((N + Q\sqrt N)\log N\bigr)\)
  • Space Complexity: \(O(N)\) (for storing each value, their prefix sums, and block management information)

Since \(N, Q \le 5\times10^4\), \(Q\sqrt N \approx 5\times10^4 \times 224 \approx 1.1\times10^7\), which is small enough to run well within the time limit.

Implementation Points

• By unifying the state into the difference array \(C_i = B_i - A_i\), we can consolidate the two types of operations into a single signed interval addition (\(+X\) if \(T=1\), and \(-X\) if \(T=2\)). This is the key to keeping the implementation clean.

• Never reconstruct the sorted array for intermediate blocks. Only update the lazy value \(Lz\), and calculate the contribution using binary search + prefix sums. Re-sorting every time here would degrade the time complexity.

• When updating a partial block, you must apply the accumulated lazy value \(Lz\) to the actual values first, then add \(\delta\), and finally re-sort. If you do this in the wrong order, the values will be incorrect.

• The contribution formula (pre[-1] - pre[i0]) + cnt * Lz is the “sum of elements greater than \(-Lz\)” plus “their count multiplied by \(Lz\)”, which precisely equals \(\sum \max(0, v_i + Lz)\).

• The answer can be up to around \(10^{18}\), but in Python, integers have arbitrary precision, so there is no need to worry about overflow.

  Source Code

import sys
import bisect

def main():
    data = sys.stdin.buffer.read().split()
    pos = 0
    N = int(data[pos]); pos += 1
    Q = int(data[pos]); pos += 1

    base = [0] * N
    for i in range(N):
        a = int(data[pos]); b = int(data[pos + 1]); pos += 2
        base[i] = b - a

    bs = max(1, int(N ** 0.5))
    nb = (N + bs - 1) // bs

    blk_vals = []
    blk_pre = []
    blk_lazy = [0] * nb
    blk_contrib = [0] * nb

    for k in range(nb):
        s = k * bs
        e = N if s + bs > N else s + bs
        v = sorted(base[s:e])
        pre = [0] * (len(v) + 1)
        acc = 0
        for t in range(len(v)):
            acc += v[t]
            pre[t + 1] = acc
        blk_vals.append(v)
        blk_pre.append(pre)

    total = 0
    bisect_right = bisect.bisect_right
    for k in range(nb):
        v = blk_vals[k]
        pre = blk_pre[k]
        i0 = bisect_right(v, 0)
        c = pre[-1] - pre[i0]
        blk_contrib[k] = c
        total += c

    out = []

    def apply_partial(k, lo, hi, delta):
        nonlocal total
        s = k * bs
        e = N if s + bs > N else s + bs
        L = blk_lazy[k]
        if L:
            for i in range(s, e):
                base[i] += L
            blk_lazy[k] = 0
        if delta:
            for i in range(lo, hi + 1):
                base[i] += delta
        v = sorted(base[s:e])
        pre = [0] * (len(v) + 1)
        acc = 0
        for t in range(len(v)):
            acc += v[t]
            pre[t + 1] = acc
        blk_vals[k] = v
        blk_pre[k] = pre
        i0 = bisect_right(v, 0)
        newc = pre[-1] - pre[i0]
        total += newc - blk_contrib[k]
        blk_contrib[k] = newc

    for _ in range(Q):
        T = int(data[pos]); L = int(data[pos + 1]); R = int(data[pos + 2]); X = int(data[pos + 3])
        pos += 4
        delta = X if T == 1 else -X
        l = L - 1
        r = R - 1
        bl = l // bs
        br = r // bs
        if bl == br:
            apply_partial(bl, l, r, delta)
        else:
            apply_partial(bl, l, (bl + 1) * bs - 1, delta)
            apply_partial(br, br * bs, r, delta)
            for k in range(bl + 1, br):
                blk_lazy[k] += delta
                Lz = blk_lazy[k]
                v = blk_vals[k]
                pre = blk_pre[k]
                i0 = bisect_right(v, -Lz)
                cnt = len(v) - i0
                newc = (pre[-1] - pre[i0]) + cnt * Lz
                total += newc - blk_contrib[k]
                blk_contrib[k] = newc
        out.append(str(total))

    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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