Day 047-Q1 — 区間Chmin+加算融合SegTree（Segment Tree Beats）

2026-05-31 赤色 Master / Phase 8+ ★★★★★★★★★ Segment Tree Beats / Ji Driver Segmentation

問題

$N$ 個の整数列 $a_1, \ldots, a_N$（初期値すべて $0$）に対して以下の $Q$ クエリを処理せよ：

  • 1 l r v：$a_l, \ldots, a_r$ に整数 $v$ を加算する
  • 2 l r v：$a_l, \ldots, a_r$ の各要素を $\min(a_i, v)$ に更新する（区間 chmin）
  • 3 l r：$\sum_{i=l}^{r} a_i$ を出力する

制約

$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$-10^9 \le v \le 10^9$
$1 \le l \le r \le N$
時間制限: 3秒

入出力例

入力例 1

5 5
1 1 5 3
2 2 4 4
3 1 5
1 3 5 2
3 1 5

出力例 1

14
18

概念図: Segment Tree Beats のノード構造

ノード [1..8] max_val=5, max_cnt=2, second_max=4 sum=30, lazy_add=0, lazy_chmin=∞ 「最大値・個数・第二最大値・和」を同時管理 ← chmin(v=4) v > second_max かつ v < max_val → O(1) で最大値のみ更新 更新後 [1..8] max_val=4, max_cnt=2, second_max=4 sum=28 (= 30 - (5-4)*2), lazy_chmin=4 chmin(v) の処理条件 v ≥ max_val → 変化なし（即リターン） second_max < v < max_val → O(1) で最大値のみ更新 + lazy_chmin=v v ≤ second_max → 子へ分割伝播（最悪ケース、amortized O(log²N)）

ヒント（段階的開示）

ヒント1: 方向性
区間加算と区間 chmin が混在する問題は通常の遅延セグメント木では対処できません。「Segment Tree Beats（Ji Driver Segmentation）」という拡張手法を考えましょう。各ノードに最大値・最大値カウント・第二最大値・区間和・遅延加算値・遅延chmin値を持たせます。
ヒント2: アプローチ
  • 各ノードに保持: max_val（区間最大値）, max_cnt（最大値の個数）, second_max（第二最大値）, sum_val（区間和）, lazy_add（遅延加算）, lazy_chmin（遅延chmin、初期値+∞）
  • 区間 chmin(v): $v \ge \text{max\_val}$ なら変化なし；$v > \text{second\_max}$ なら最大値のみ $v$ に変更 $O(1)$；それ以外は子に分割伝播
  • 区間加算: 通常の遅延加算と同様、ただし lazy_chmin にも加算する
ヒント3: 実装骨格 
def apply_add(self, i, v, length):
    nd = self.node[i]
    nd.sum_val += v * length
    nd.max_val += v
    if nd.second_max != -INF:
        nd.second_max += v
    nd.lazy_add += v
    if nd.lazy_chmin != INF:
        nd.lazy_chmin += v

def apply_chmin(self, i, v):
    nd = self.node[i]
    if v >= nd.max_val:
        return
    nd.sum_val -= (nd.max_val - v) * nd.max_cnt
    nd.max_val = v
    nd.lazy_chmin = min(nd.lazy_chmin, v)

模範解答 (Python)

import sys
input = sys.stdin.readline

INF = float('inf')

class Node:
    __slots__ = ('max_val','max_cnt','second_max','sum_val','lazy_add','lazy_chmin')
    def __init__(self, size=0):
        self.max_val = 0
        self.max_cnt = size
        self.second_max = -INF
        self.sum_val = 0
        self.lazy_add = 0
        self.lazy_chmin = INF

class SegTreeBeats:
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size <<= 1
        self.node = [Node() for _ in range(2 * self.size)]
        for i in range(self.size):
            self.node[self.size + i].max_cnt = 1

    def push_up(self, i):
        l, r = 2*i, 2*i+1
        nd = self.node
        nd[i].sum_val = nd[l].sum_val + nd[r].sum_val
        if nd[l].max_val == nd[r].max_val:
            nd[i].max_val = nd[l].max_val
            nd[i].max_cnt = nd[l].max_cnt + nd[r].max_cnt
            nd[i].second_max = max(nd[l].second_max, nd[r].second_max)
        elif nd[l].max_val > nd[r].max_val:
            nd[i].max_val = nd[l].max_val
            nd[i].max_cnt = nd[l].max_cnt
            nd[i].second_max = max(nd[l].second_max, nd[r].max_val)
        else:
            nd[i].max_val = nd[r].max_val
            nd[i].max_cnt = nd[r].max_cnt
            nd[i].second_max = max(nd[l].max_val, nd[r].second_max)

    def apply_add(self, i, v, length):
        nd = self.node[i]
        nd.sum_val += v * length
        nd.max_val += v
        if nd.second_max != -INF:
            nd.second_max += v
        nd.lazy_add += v
        if nd.lazy_chmin != INF:
            nd.lazy_chmin += v

    def apply_chmin(self, i, v):
        nd = self.node[i]
        if v >= nd.max_val:
            return
        nd.sum_val -= (nd.max_val - v) * nd.max_cnt
        nd.max_val = v
        nd.lazy_chmin = min(nd.lazy_chmin, v)

    def push_down(self, i, length):
        nd = self.node
        half = length >> 1
        if nd[i].lazy_add != 0:
            self.apply_add(2*i, nd[i].lazy_add, half)
            self.apply_add(2*i+1, nd[i].lazy_add, half)
            nd[i].lazy_add = 0
        if nd[i].lazy_chmin != INF:
            self.apply_chmin(2*i, nd[i].lazy_chmin)
            self.apply_chmin(2*i+1, nd[i].lazy_chmin)
            nd[i].lazy_chmin = INF

    def _update_add(self, node, l, r, ql, qr, v, length):
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.apply_add(node, v, length)
            return
        self.push_down(node, length)
        mid = (l + r) >> 1
        self._update_add(2*node, l, mid, ql, qr, v, length >> 1)
        self._update_add(2*node+1, mid+1, r, ql, qr, v, length >> 1)
        self.push_up(node)

    def _update_chmin(self, node, l, r, ql, qr, v, length):
        if qr < l or r < ql or v >= self.node[node].max_val:
            return
        if ql <= l and r <= qr and v > self.node[node].second_max:
            self.apply_chmin(node, v)
            return
        self.push_down(node, length)
        mid = (l + r) >> 1
        self._update_chmin(2*node, l, mid, ql, qr, v, length >> 1)
        self._update_chmin(2*node+1, mid+1, r, ql, qr, v, length >> 1)
        self.push_up(node)

    def _query_sum(self, node, l, r, ql, qr, length):
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.node[node].sum_val
        self.push_down(node, length)
        mid = (l + r) >> 1
        return (self._query_sum(2*node, l, mid, ql, qr, length >> 1) +
                self._query_sum(2*node+1, mid+1, r, ql, qr, length >> 1))

    def add(self, l, r, v):
        self._update_add(1, 1, self.size, l, r, v, self.size)

    def chmin(self, l, r, v):
        self._update_chmin(1, 1, self.size, l, r, v, self.size)

    def query(self, l, r):
        return self._query_sum(1, 1, self.size, l, r, self.size)


def main():
    N, Q = map(int, input().split())
    seg = SegTreeBeats(N)
    out = []
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            seg.add(q[1], q[2], q[3])
        elif q[0] == 2:
            seg.chmin(q[1], q[2], q[3])
        else:
            out.append(seg.query(q[1], q[2]))
    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

1Segment Tree Beats の基本思想
通常の遅延セグメント木は「各要素に同一変換を適用する」場合に機能する。区間 chmin は要素により変化量が異なるため直接遅延できない。「第二最大値より大きい chmin クエリは最大値のみを変化させる」性質を利用して $O(1)$ 処理。
2ノードの設計
各ノードに max_val, max_cnt, second_max, sum_val を保持する。sum_val の変化量は (max_val - v) * max_cnt で計算できる。
3遅延伝播の設計
加算 lazy と chmin lazy を組み合わせる。push_down では加算を先に伝播してから chmin を伝播する順序を守る。
4計算量解析
区間 chmin の amortized 計算量は勢位関数解析で $O(N \log^2 N)$。全体 $O(Q \log^2 N)$。
5push_down 時の length 管理
セグメント木の各ノードが管理する区間長を引数で渡す。apply_add では length を使い sum を更新する。

計算量

構築: $O(N)$
区間加算: $O(\log N)$ amortized
区間 chmin: $O(\log^2 N)$ amortized
区間和クエリ: $O(\log N)$
全体: $O(Q \log^2 N)$

よくあるミス

ミス原因正しい書き方
second_max の初期値が 0全要素 0 の時に chmin が誤動作second_max = -INF
加算後に lazy_chmin を更新しないchmin 値がずれるlazy_chmin += v も忘れずに
push_down の順序を誤るchmin を先に伝播すると加算後に chmin が正しくない加算 → chmin の順で伝播
chmin で second_max < v < max_val の判定ミス子に分割せず誤って適用v > second_max の条件を厳密に

次のステップ

  • 発展問題: 区間 chmax も加えた「Ji Driver Segmentation」完全版
  • 関連: Day035 Q1（Segment Tree Beats 実際更新カウント）の復習
  • 応用: 機械学習の特徴量クランプ処理の高速化

自己評価