E - 倉庫の在庫管理 / Warehouse Inventory Management Editorial by admin
gpt-5.5-high概要
\(D_i = B_i - A_i\) とおくと、求めたい値は \(\sum_i \max(0, D_i)\) です。
報告は区間に対して \(D_i\) を加算または減算する操作なので、「区間加算」と「正の部分の総和」を高速に管理します。
考察
まず、各倉庫について重要なのは \(A_i, B_i\) そのものではなく、差分
\(D_i = B_i - A_i\)
です。
不足分は \(\max(0, D_i)\) なので、答えは
\(\sum_{i=1}^{N} \max(0, D_i)\)
です。
報告による変化は次のように言い換えられます。
- \(T_j = 1\)：\(B_i\) が \(X_j\) 増える
→ \(D_i\) が \(X_j\) 増える - \(T_j = 2\)：\(A_i\) が \(X_j\) 増える
→ \(D_i\) が \(X_j\) 減る
つまり、問題は次の形になります。
数列 \(D\) に対して区間加算を行い、毎回 \(\sum \max(0, D_i)\) を求める。
素朴に各クエリで区間内の全要素を更新し、その後全体を集計すると \(O(NQ)\) かかります。
\(N, Q \leq 5 \times 10^4\) なので、最大で \(2.5 \times 10^9\) 回程度の処理になり、間に合いません。
そこで、平方分割を使います。
数列をいくつかのブロックに分け、ブロック全体に対する更新はまとめて処理します。
各ブロックでは、要素をソートした配列と累積和を持っておくことで、
\(\sum \max(0, D_i)\)
を高速に再計算できます。
アルゴリズム
\(D_i = B_i - A_i\) を配列として持ちます。
配列を長さ \(K\) 程度のブロックに分割します。
実装では \(K = 256\) としています。
各ブロックについて、次の情報を管理します。
arr[i]：各要素の値lazy[b]：ブロック全体に加えられている遅延加算値sblocks[b]：ブロック内のarrをソートしたものprefs[b]：sblocks[b]の累積和bsum[b]：そのブロックにおける \(\sum \max(0, D_i)\)total：全ブロックのbsumの合計、つまり現在の答え
ここで、実際の値は
\(arr[i] + lazy[b]\)
です。
ブロック全体を更新する場合
ブロック全体に \(\delta\) を加算する場合を考えます。
- \(T = 1\) なら \(\delta = X\)
- \(T = 2\) なら \(\delta = -X\)
ブロック全体への加算なので、arr[i] は直接変更せず、lazy[b] に \(\delta\) を足します。
その後、そのブロックの
\(\sum \max(0, arr[i] + lazy[b])\)
を計算します。
ブロック内の値をソートした配列を \(v\) とします。
正の値になる条件は
\(v + lazy[b] > 0\)
つまり
\(v > -lazy[b]\)
です。
ソート済み配列に対して二分探索を行い、\(v \leq -lazy[b]\) となる最後の位置を求めます。
それより後ろの要素だけが正の値になります。
正になる要素の個数を \(cnt\)、それらの arr の合計を \(sum\) とすると、ブロックの不足分合計は
\(sum + lazy[b] \times cnt\)
です。
累積和を持っているので、\(sum\) は \(O(1)\)、境界位置は二分探索で \(O(\log K)\) で求められます。
ブロックの一部だけを更新する場合
区間の端など、ブロックの一部だけが更新対象になる場合は、その部分の要素を直接更新します。
各要素について、更新前の実際の値を
\(old = arr[i] + lazy[b]\)
更新後の値を
\(new = old + \delta\)
とすると、答えへの変化量は
\(\max(0, new) - \max(0, old)\)
です。
これを bsum[b] と total に反映します。
また、arr[i] を \(\delta\) 増やします。
ただし、この操作をすると、ブロック内のソート済み配列 sblocks[b] が古くなります。
そのため、そのブロックに dirty フラグを立てておきます。
次にそのブロックを「ブロック全体更新」で使う前に、必要ならソート済み配列と累積和を作り直します。
クエリ処理
各クエリの区間 \([L, R]\) に対して、以下のように処理します。
- \(T=1\) なら \(\delta = X\)、\(T=2\) なら \(\delta = -X\) とする
- 区間が含むブロックを調べる
- 左端・右端の中途半端な部分は、要素ごとに直接更新する
- 完全に含まれるブロックは、遅延加算と二分探索でまとめて更新する
totalを出力する
計算量
ブロックサイズを \(K\) とします。
- 部分的なブロック更新は高々 2 ブロックなので \(O(K)\)
- 完全に含まれるブロックは高々 \(O(N/K)\) 個で、それぞれ二分探索に \(O(\log K)\)
dirtyなブロックの再構築は \(O(K \log K)\) ですが、部分更新があったブロックに対して必要なときだけ行うため、全体でならして扱えます
したがって、1 クエリあたりならしで
\(O\left(K \log K + \frac{N}{K}\log K\right)\)
程度です。
\(K \approx \sqrt{N}\) とすると、
- 時間計算量: \(O(Q \sqrt{N} \log N)\) 程度
- 空間計算量: \(O(N)\)
です。
実装では \(K = 256\) としており、\(N, Q \leq 5 \times 10^4\) に十分高速です。
実装のポイント
arr[i] は実際の値そのものではなく、ブロックの lazy を除いた値として扱います。
実際の値は常に
\(arr[i] + lazy[b]\)
です。
部分更新では lazy を反映してから更新するのではなく、arr[i] に直接 \(\delta\) を加えます。
これにより、実際の値も正しく \(\delta\) だけ変化します。
また、正の部分だけを足すため、二分探索では
\(v + lazy > 0\)
すなわち
\(v > -lazy\)
となる最初の位置を求めます。
値がちょうど \(0\) のものは不足分に含まれないため、bisect_right を使っています。
答えは最大で \(10^{18}\) になるため、他言語では 64 bit 整数型を使う必要があります。Python では整数が任意精度なのでそのままで問題ありません。
ソースコード
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()
この解説は gpt-5.5-high によって生成されました。
posted:
last update: