題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🌈 AWC0104E Warehouse Inventory Management

Problem Statement

題目簡述

有 $N$ 個倉庫，第 $i$ 個倉庫目前有 $A_i$ 件庫存，未來訂單預計需要 $B_i$ 件。
接著有 $Q$ 筆報告，每筆報告會對一段連續倉庫做以下其中一種操作：

$T=1$ ：新訂單增加，區間內每個倉庫的需求量 $B_i$ 都增加 $X$ 。
$T=2$ ：新進貨抵達，區間內每個倉庫的庫存量 $A_i$ 都增加 $X$ 。

每次操作後，輸出所有倉庫短缺量的總和：

\sum_{i=1}^{N}\max(0,B_i-A_i)

Constraints

約束條件

$1\le N\le 5\times 10^4$
$1\le Q\le 5\times 10^4$
$0\le A_i,B_i\le 10^7$
$T_j\in\{1,2\}$
$1\le L_j\le R_j\le N$
$1\le X_j\le 10^7$
每個輸出值不超過 $10^{18}$
所有輸入皆為整數。

思路：差值正部總和 + 根號分治

這題的操作同時提到庫存與需求，但真正影響答案的只有兩者的差值。把每個倉庫的狀態改寫成「需求量減庫存量」後，所有操作都會變成同一種形式：對一段連續位置加上一個值。

令差值為

C_i=B_i-A_i

答案就是差值的正部總和：

\sum_i \max(0,C_i)

收到新訂單時，區間內的差值整段增加；收到新進貨時，區間內的差值整段減少。於是問題變成：

題型轉換

維護一個數列，支援區間加值；每次操作後，詢問全體元素的正部總和。

如果每次更新後都掃過整個數列，單次操作是 $\mathcal{O}(N)$ ，在 $N,Q\le 5\times 10^4$ 時不可行。接下來的關鍵是：如何只重算受影響的部分，又能知道哪些元素在加值後跨過 $0$ 。

Lazy Segment Tree 的侷限

看到「區間加值 + 全域查詢」，很自然會先想到 Lazy Segment Tree。但 Lazy Segment Tree 能高效運作有一個前提：節點資訊在套上懶標記後，可以直接用公式推算出新的節點資訊。

例如區間總和：節點維護的區間長度為 $L$ ，原始總和為 $S$ ，整段加 $v$ 後，新總和就是 $S+v\cdot L$ 。公式只需要 $S$ 、 $L$ 、 $v$ 三個量，不需要知道區間內每個元素的值。

但 $\sum\max(0,x)$ 不是線性的—— $\max(0,a+b)\neq\max(0,a)+\max(0,b)$ 。因此「加 $v$ 後的正部總和」無法從原本的正部總和、最大值、最小值這些節點資訊推出來。

具體反例

考慮兩組 $C_i$ 值：

	C₁	C₂	C₃	C₄	總和	正部總和
狀態 A	−5	+3	+1	+1	0	5
狀態 B	−1	−1	+1	+1	0	2

總和相同（都是 $0$ ），但加 $2$ 後：

	C₁	C₂	C₃	C₄	總和	正部總和
狀態 A+2	−3	+5	+3	+3	8	11
狀態 B+2	+1	+1	+3	+3	8	8

加完後總和相同（ $8$ ），正部總和卻不同（ $11$ vs $8$ ）。只靠總和、長度、懶標記這三個資訊，根本無法區分。

關鍵瓶頸

真正需要知道的是：有多少元素在更新後跨過 $0$ ？這取決於區間內的值分布，不是只靠總和、最大值、最小值等少量節點資訊就能完整描述的。

根號分治：保留排序後分布，分塊維護

既然瓶頸是「不知道哪些元素會跨過 $0$ 」，就需要保留局部區間內的值排序後的分布。

直接排序整個陣列顯然是不行的，因為每次對子區間更新都有可能會破壞順序，若每次更新完都重新排序，這樣開銷太大了。

但如果只看一個被完整覆蓋的塊，整塊加值只是把塊內所有值一起平移，相對大小與排序結果都不會改變。於是可以把數列切成大小為 $S$ 的區塊，在「整塊懶更新」和「邊界暴力重建」之間取得平衡。

區間更新 + 需要知道值的排序分布 → 根號分治：

完整覆蓋的塊：只改整塊偏移量，不動內部元素；
邊界零散位置：直接修改基準值後重建該塊；

每個區塊維護的資訊

對於每個位置，保留一個尚未套用整塊偏移量的基準值 $D_i$ 。若該位置所在塊的整體偏移量為 $\textit{lazy}$ ，則真正的差值為：

C_i = D_i+\textit{lazy}

每個塊保存三類資訊：

塊內基準值的排序結果 $sorted = [D_{i_1}, D_{i_2}, \ldots, D_{i_k}]$ ，用來二分找出非負元素的起點。
排序後基準值的前綴和 $presum$ ，用來快速計算一段後綴的總和。
一個整塊偏移量 $\textit{lazy}$ ，記錄這個塊被完整加過多少，也就是尚未逐一寫回塊內元素的懶標記。

完整覆蓋一個塊時，不需要動塊內每個元素，也不需要重新排序，只改整個區塊偏移量 $\textit{lazy}$ 就好。

用二分 + 前綴和計算貢獻

對某個塊，只有真正差值 $\ge 0$ 的元素會產生貢獻，也就是滿足

D_i + \textit{lazy} \ge 0

的元素會產生貢獻。等價地， $D_i \ge -\textit{lazy}$ 。

由於塊內基準值已排序，可以使用二分搜尋找到第一個不小於 $-\textit{lazy}$ 的位置。設從該位置到塊尾有 $k$ 個元素，整個塊的貢獻就是：

\sum D_i+k\cdot\textit{lazy}

其中 $\sum D_i$ 是這段後綴的基準值總和，可以在重建區塊時預處理前綴和，使得在計算時可以 $\mathcal{O}(1)$ 算出；二分本身需要 $\mathcal{O}(\log S)$ 。

區間更新

區間更新時，如何維護答案？

對任何被修改的塊，都可以先扣掉更新前的舊貢獻，再加上更新後的新貢獻，這樣就能正確維護全域答案。

ans = ans - \textit{old} + \textit{new}

因為每個區塊在更新前後都能重新取得「排序 + 前綴和」資訊，所以每次只要重算受影響區塊的貢獻，不必重新掃過整個數列。

對於每一次更新，可以分兩部分處理：

1. 完整覆蓋的塊

整個塊都被加上同一個值時，塊內元素的相對順序不變，因此只需要：

扣掉這個塊更新前的貢獻。
修改整塊偏移量。
加回更新後的貢獻。

這一類塊不用重建排序結果。

2. 邊界不完整的塊

左右兩端通常只會更新塊中的一部分位置，這會破壞原本排序結果所代表的值分布。因此需要逐一修改受影響位置的基準值，最後重建排序結果與前綴和。

實作細節

部分更新只會額外改動被選中的位置，所以直接把差值 $v$ 寫到這些位置的基準值即可；原本的整塊偏移量 $\textit{lazy}$ 仍然保留。

重建時排序的是更新後的基準值，計算貢獻時再一起加上這個塊原本的偏移量。

區塊大小 $S$ 的選擇

每次操作最多兩個邊界塊需要暴力重建，代價 $\mathcal{O}(S\log S)$ 。中間完整覆蓋的塊最多 $\mathcal{O}(\frac{N}{S})$ 個，每個區塊只需要做兩次二分，每次二分代價為 $\mathcal{O}(\log S)$ 。

因此單次操作的代價為：

\mathcal{O}\left(S\log S+\frac{N}{S}\log S\right) = \mathcal{O}\left((S+\frac{N}{S})\log S\right)

忽略 $\log S$ 項，我們想要最小化 $S+\frac{N}{S}$ ，可以取 $S=\sqrt N$ ，每次操作約 $\mathcal{O}(\sqrt N\log N)$ 。

複雜度分析

時間複雜度：每次 $\mathcal{O}(\sqrt N\log N)$ ，總 $\mathcal{O}(Q\sqrt N\log N)$
空間複雜度： $\mathcal{O}(N)$

Code

提交方式

這份程式需要使用 Python（Codon 0.19.3）提交，使用 CPython 或 PyPy 都會 TLE。

Codon 與原生 Python 的差異

Codon 會做靜態型別推斷與編譯，因此某些在原生 Python 中可行的寫法，可能需要改成更明確的形式。以下是我踩過的坑：

map(...) 在 Codon 中會被視為 Generator，不能直接解包，需先轉成 list。
[[] for _ in range(m)] 可能被推斷成 List[List[NoneType]]，巢狀整數列表要給 Codon 明確型別線索。
使用巢狀函式自動捕獲函式內的可變狀態時，Codon 不一定能編譯；這份程式因此改用全域變數保存可變狀態。

from bisect import bisect_left
from itertools import accumulate


n, q = list(map(int, input().split()))
C: list[int] = []
for _ in range(n):
    # a, b = map(int, input().split())
    a, b = list(map(int, input().split()))
    C.append(b - a)

# B = isqrt(n) + 1
B = int(n**0.5) + 1
m = (n + B - 1) // B  # ceil(n / B)

bucket: list[list[int]] = [[] for _ in range(m)]
presum: list[list[int]] = [[] for _ in range(m)]
lazy: list[int] = [0] * m
ans = sum(max(0, x) for x in C)


def build(b: int) -> None:
    l = b * B
    r = min(n, (b + 1) * B)
    bucket[b] = sorted(C[l:r])
    presum[b] = list(accumulate(bucket[b], initial=0))


def count(b: int) -> int:
    A = bucket[b]
    ps = presum[b]
    idx = bisect_left(A, -lazy[b])
    cnt = len(A) - idx
    return ps[-1] - ps[idx] + cnt * lazy[b]


def add(b: int, l: int, r: int, v: int) -> None:
    global ans
    ans -= count(b)
    for i in range(l, r + 1):
        C[i] += v
    build(b)
    ans += count(b)


for b in range(m):
    build(b)


for _ in range(q):
    op, l, r, v = list(map(int, input().split()))
    l, r = l - 1, r - 1
    if op == 2:
        v = -v

    bl, br = l // B, r // B
    if bl == br:
        add(bl, l, r, v)
    else:
        add(bl, l, (bl + 1) * B - 1, v)
        add(br, br * B, r, v)
        for b in range(bl + 1, br):
            ans -= count(b)
            lazy[b] += v
            ans += count(b)
    print(ans)

寫在最後

Cover Image Credit

The cover image was created by @Rosuuri. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.

🔗 🌈 AWC0104E Warehouse Inventory Management

Problem Statement

Constraints

思路：差值正部總和 + 根號分治

Lazy Segment Tree 的侷限

根號分治：保留排序後分布，分塊維護

每個區塊維護的資訊

用二分 + 前綴和計算貢獻

區間更新

1. 完整覆蓋的塊

2. 邊界不完整的塊

區塊大小 SSS 的選擇

複雜度分析

Code

寫在最後

區塊大小 $S$ 的選擇