問題
長さ $N$ の整数列 $A=(A_0,\dots,A_{N-1})$ がある。各要素について「これまでに一度でも取ったことのある最大値」を $\mathrm{hist}_i$ と呼ぶ（初期値は $\mathrm{hist}_i=A_i$）。以下の3種類のクエリを $Q$ 個処理せよ。
1 l r x: $i\in[l,r)$ について $A_i \leftarrow \min(A_i,x)$（区間 chmin）2 l r x: $i\in[l,r)$ について $A_i \leftarrow A_i+x$（区間 add、$x$ は負でもよい）3 l r: $\max_{i\in[l,r)}\mathrm{hist}_i$ を出力
chmin は $A_i$ を下げるだけだが、$\mathrm{hist}_i$ は一度到達した最大値を chmin で失わない点に注意する。
入力形式
N Q
A_0 A_1 ... A_{N-1}
query_1
...
query_Q制約
$1 \le N \le 2\times10^4$
$1 \le Q \le 2\times10^4$
$-10^6 \le A_i, x \le 10^6$
$0 \le l < r \le N$
入出力例
入力例1
6 6
5 3 8 1 9 2
3 0 6
2 0 3 10
3 0 3
1 0 3 12
3 0 3
3 3 6出力例1
9
18
18
9最初の add で $[0,3)$ に $+10$ → $A=[15,13,18,1,9,2]$ となり、この時点で $\mathrm{hist}$ も更新される。続く chmin で $A$ は $[12,12,12,\dots]$ に下がるが、$\mathrm{hist}$ の記録（18 など）は失われない。
概念図：ブロックごとの4つの要約値
ヒント（段階的開示）
ヒント1（方向性）
$\mathrm{hist}_i$ は「今までの $A_i$ の推移の最大値」であり、add は増やしうるが chmin は決して増やせない。まず区間全体を毎回 $O(N)$ で舐める素朴な方法を思い浮かべ、それをブロック単位に要約して高速化する方向で考える。
ヒント2（アプローチ）
add はブロック丸ごと $O(1)$ の遅延タグにできる。しかし chmin はブロック内の要素ごとに効果が異なる（$x$ を超える要素だけ下がる）ので、丸ごと $O(1)$ で処理できるのは「ブロックの現在の最大値がそもそも $x$ 以下」の場合だけ。それ以外は諦めてブロックの中身を実際に展開（マテリアライズ）する。
ヒント3（誘導）
加算を追加するときは先に hist_add_lazy = max(hist_add_lazy, add_lazy + x)、その後で add_lazy += x する（順序が肝）。クエリ時のブロックの「今の歴代最大」は
で $O(1)$ に求まる（生値のランキングが加算で保たれるため、生値最大の要素がそのブロックの記録更新のピークを実現する）。
模範解答 (Python)
import sys, math
def solve():
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
q = int(data[idx]); idx += 1
a = [int(data[idx + i]) for i in range(n)]; idx += n
B = max(1, int(math.isqrt(n)) + 1)
nb = (n + B - 1) // B
raw = a[:]
hist = a[:]
add_lazy = [0] * nb
hist_add_lazy = [0] * nb
block_max_raw = [0] * nb
HM_stored = [0] * nb
def block_range(b):
lo = b * B
return lo, min(n, lo + B)
for b in range(nb):
lo, hi = block_range(b)
block_max_raw[b] = max(raw[lo:hi])
HM_stored[b] = max(hist[lo:hi])
def materialize(b):
al, hal = add_lazy[b], hist_add_lazy[b]
if al == 0 and hal == 0:
return
lo, hi = block_range(b)
for i in range(lo, hi):
peak = raw[i] + hal
if peak > hist[i]:
hist[i] = peak
raw[i] += al
add_lazy[b] = 0
hist_add_lazy[b] = 0
block_max_raw[b] = max(raw[lo:hi])
HM_stored[b] = max(hist[lo:hi])
def touch_add(b, lo, hi, x):
materialize(b)
for i in range(lo, hi):
raw[i] += x
if raw[i] > hist[i]:
hist[i] = raw[i]
blo, bhi = block_range(b)
block_max_raw[b] = max(raw[blo:bhi])
HM_stored[b] = max(hist[blo:bhi])
def range_add(l, r, x):
bl, br = l // B, (r - 1) // B
if bl == br:
touch_add(bl, l, r, x); return
touch_add(bl, l, (bl + 1) * B, x)
touch_add(br, br * B, r, x)
for b in range(bl + 1, br):
hist_add_lazy[b] = max(hist_add_lazy[b], add_lazy[b] + x)
add_lazy[b] += x
def touch_chmin(b, lo, hi, x):
materialize(b)
for i in range(lo, hi):
if raw[i] > x:
raw[i] = x
blo, bhi = block_range(b)
block_max_raw[b] = max(raw[blo:bhi])
HM_stored[b] = max(hist[blo:bhi])
def range_chmin(l, r, x):
bl, br = l // B, (r - 1) // B
if bl == br:
touch_chmin(bl, l, r, x); return
touch_chmin(bl, l, (bl + 1) * B, x)
touch_chmin(br, br * B, r, x)
for b in range(bl + 1, br):
true_max = block_max_raw[b] + add_lazy[b]
if x >= true_max:
continue
materialize(b)
blo, bhi = block_range(b)
for i in range(blo, bhi):
if raw[i] > x:
raw[i] = x
block_max_raw[b] = max(raw[blo:bhi])
HM_stored[b] = max(hist[blo:bhi])
def query(l, r):
bl, br = l // B, (r - 1) // B
if bl == br:
materialize(bl)
return max(hist[l:r])
materialize(bl)
best = max(hist[l:(bl + 1) * B])
materialize(br)
best = max(best, max(hist[br * B:r]))
for b in range(bl + 1, br):
best = max(best, HM_stored[b], block_max_raw[b] + hist_add_lazy[b])
return best
out = []
for _ in range(q):
t = data[idx]; idx += 1
if t == '1':
l, r, x = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
range_chmin(l, r, x)
elif t == '2':
l, r, x = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
range_add(l, r, x)
else:
l, r = int(data[idx]), int(data[idx+1]); idx += 2
out.append(str(query(l, r)))
print('\n'.join(out))
solve()Step-by-Step 解説
1chminをブロック丸ごと処理できない理由
区間 add はブロック全体に同じ量を足すので遅延タグ1個で済むが、区間 chmin は要素ごとに効果が違う非一様な操作。ブロックの現在の最大値が $x$ 以下なら何もしない（$O(1)$スキップ）、そうでなければ展開して1要素ずつ処理する。
区間 add はブロック全体に同じ量を足すので遅延タグ1個で済むが、区間 chmin は要素ごとに効果が違う非一様な操作。ブロックの現在の最大値が $x$ 以下なら何もしない（$O(1)$スキップ）、そうでなければ展開して1要素ずつ処理する。
2歴代最大値のための2本のタグ
add_lazyは「まだ反映していない加算量」、hist_add_lazyは「その加算が積み重なる過程で一瞬でも到達した最大の増分」。新しい加算 $x$ が来たときhist_add_lazy = max(hist_add_lazy, add_lazy + x)を先に計算してからadd_lazy += xする。3クエリ時のO(1)合成が成り立つ理由
遅延期間中
遅延期間中
raw[i] は全要素が同じ量だけ加算され続けるので大小関係は変わらない。よって「raw[i]+hist_add_lazyの最大値」はraw最大の要素で実現され、block_max_raw + hist_add_lazy が正しい。これと事前確定していたHM_storedの大きい方（max、sumではない）を取る。4実測（本ページ作成時にPythonで実行）
| テスト内容 | 結果 |
|---|---|
| 手動トレース（入力例1） | fast [9,18,18,9] / naive [9,18,18,9] 一致 |
| ランダム300件（N≤40, 演算60回） | naiveとの不一致 0件 |
| N=Q=4000 | 平方分割 0.066s / naive 0.112s（約1.7倍） |
| N=Q=20000（B=142） | 平方分割 0.873s / naive 3.008s（約3.44倍） |
迷った他案と採らなかった理由
| 案 | 採否 | 理由 |
|---|---|---|
| Segment Tree Beats Ver.2（max1/max2バケット分離＋歴代加算タグ、$O(N\log^2 N)$償却） | 不採用 | これが本来の実問題（Luogu P6242「线段树3」相当）の正攻法だが、複数バケットの同時 push down ロジックはバグを埋め込みやすく、限られた検証時間で正しさを保証しにくいと判断した |
| 平方分割（$O((N+Q)\sqrt N)$、本ページの採用案） | 採用 | 実装がシンプルでブルートフォースとの突き合わせが容易。$N,Q\le2\times10^4$ 程度なら実用上十分な速度（実測3.44倍） |
| chmin を毎回ブロック内で必ずマテリアライズする単純版 | 不採用 | 「block_max_raw+add_lazy ≥ x のときだけ潜る」スキップを入れないと chmin のたびに全ブロックを展開してしまい、平方分割の利点が消える |
本来のSegment Tree Beats Ver.2との漸近計算量の差は、実装の正しさを検証しやすくするために払ったコストとして明記する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
hist_add_lazyを先にadd_lazyに加算してから更新 | 順序を逆にすると直前の記録を見落とす | hist_add_lazy=max(hist_add_lazy, add_lazy+x)を先に計算 |
chminのスキップ判定をblock_max_raw≥xだけで行う | add_lazyを足し忘れ | 必ずblock_max_raw+add_lazy≥xで判定 |
クエリでHM_stored+hist_add_lazyと加算してしまう | HM_storedはMAX集約でsumできない | max(HM_stored, block_max_raw+hist_add_lazy) |
| マテリアライズ後の要約値再計算を忘れる | 遅延解消後に要約が古いまま | materialize()末尾で必ず再計算 |
次のステップ
- 関連する実問題: Luogu P6242「线段树3」（本問はそのクエリをMAX一種に単純化した簡略版で、直接の対応問題ではない）
- 発展: クエリを「区間の歴代最大値の総和」に変えるとMAX集約では通用せず、真のBeats Ver.2が必要になる理由を導出する
- 扱わなかった範囲: max1/max2バケット分離による$O(N\log^2N)$版そのもの
- 次回予告: 完全なSegment Tree Beats Ver.2への挑戦