Day 098-Q1 | Chtholly Tree（区間代入+区間和）

問題

長さ $N$ の数列 $a_1, a_2, \dots, a_N$ が与えられる。以下の2種類のクエリを $Q$ 個、順番に処理せよ。

1 l r x: 区間 $[l, r]$ の全要素を $x$ に一括代入する
2 l r: 区間 $[l, r]$ の要素の総和を出力する

区間代入クエリが多く含まれるデータに対しては、区間を「同じ値を持つ連続ブロック」の集合として管理する Chtholly Tree（Old Driver Tree, ODT） を用いると、通常のセグメント木より実装が簡潔かつ高速に動作する場合が多い。

入力形式

N Q
a_1 a_2 ... a_N
query_1
query_2
:
query_Q

制約

$1 \le N, Q \le 2 \times 10^5$

$0 \le a_i, x \le 10^9$

$1 \le l \le r \le N$

入出力例

入力例1

出力例1

15
36
30

最初のクエリは全体の和 1+2+3+4+5=15。次に [2,4] を10に代入すると数列は [1,10,10,10,5] になり、全体和は36、[2,4]の和は30。

概念図

ヒント（段階的開示）

ヒント1: 方向性

区間代入は「同じ値の連続区間をまとめて1つのブロックとして扱える」という性質を持つ。セグメント木で区間代入・区間和を両方サポートしようとすると遅延伝播が必要になるが、もっと直接的に「値ごとの区間」を管理するデータ構造は作れないか考えよ。

ヒント2: アプローチ

数列を「開始位置ごとに1つの値を持つ区間」の集合として、開始位置をキーとした辞書＋ソート済みリストで管理する。区間 $[l, r]$ に対する操作を行う前に、必ず「位置 $l$ と位置 $r+1$ を区間の境界として分割する split 操作」を行うのがポイント。分割さえできれば、代入は「範囲内の区間をすべて削除して新しい1区間を挿入」、総和は「範囲内の各区間の (長さ×値) を合計」するだけで実現できる。

ヒント3: 誘導（コード骨格）

from bisect import bisect_right, insort

starts = list(range(1, n + 1))
seg = {i: [i, i, a[i - 1]] for i in range(1, n + 1)}  # start -> [start, end, value]

def split(pos):
    i = bisect_right(starts, pos) - 1
    s = starts[i]
    st, en, val = seg[s]
    if st == pos:
        return
    seg[s] = [st, pos - 1, val]
    seg[pos] = [pos, en, val]
    insort(starts, pos)

split(l) と（$r+1 \le N$ なら）split(r+1) を先に呼んでから、区間 $[l, r]$ に対応する連続したキー群をまとめて処理する。

模範解答 (Python)

import sys
from bisect import bisect_right, insort


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

    starts = list(range(1, n + 1))
    seg = {i: [i, i, a[i - 1]] for i in range(1, n + 1)}

    def split(pos):
        i = bisect_right(starts, pos) - 1
        s = starts[i]
        st, en, val = seg[s]
        if st == pos:
            return
        seg[s] = [st, pos - 1, val]
        seg[pos] = [pos, en, val]
        insort(starts, pos)

    def assign(l, r, x):
        split(l)
        if r + 1 <= n:
            split(r + 1)
        i = bisect_right(starts, l) - 1
        j = bisect_right(starts, r) - 1
        remove_keys = starts[i:j + 1]
        for k in remove_keys:
            del seg[k]
        del starts[i:j + 1]
        seg[l] = [l, r, x]
        insort(starts, l)

    def query_sum(l, r):
        split(l)
        if r + 1 <= n:
            split(r + 1)
        i = bisect_right(starts, l) - 1
        j = bisect_right(starts, r) - 1
        total = 0
        for k in starts[i:j + 1]:
            st, en, val = seg[k]
            total += (en - st + 1) * val
        return total

    out = []
    for _ in range(q):
        t = data[idx]; idx += 1
        if t == '1':
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            x = int(data[idx]); idx += 1
            assign(l, r, x)
        else:
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            out.append(str(query_sum(l, r)))

    print('\n'.join(out))


solve()

計算量: assignで区間が減っていくため、代入クエリが十分な頻度で発生するデータに対してならし $O((N+Q)\log N)$ 程度（ポテンシャル法による解析）。

Step-by-Step 解説

1初期状態の構築
各要素を長さ1の区間として個別に管理する（seg[i]=[i,i,a[i-1]]）。starts は開始位置の昇順リスト。

2split操作
split(pos) は位置 pos を含む区間を [st,pos-1] と [pos,en] に分割する。既に境界なら何もしない。

3assign（区間代入）
境界を確定させたあと範囲内の区間を全削除し、新しい1区間 [l,r]=x を挿入する。

4query_sum（区間和）
範囲内の各区間の (長さ×値) を合計する。

5償却計算量の直感
assignのたびに区間が1つに統合されるため、区間総数は増え続けない。ポテンシャル法により、代入クエリが十分な頻度で存在すればならし計算量が抑えられることが示せる。

よくあるミス

ミス	原因	正しい書き方
`split(r+1)` を `r==N` でも呼びKeyError	存在しない位置 $N+1$ を分割しようとする	`r+1 <= n` の場合のみ `split` を呼ぶ
`del starts[i:j+1]` の前に`seg`削除を忘れる	辞書とリストの整合性が崩れる	`remove_keys` を先に取得し両方から同じキー集合を削除する
`split(r+1)` を `split(l)` より先に呼ぶ	`starts`のインデックスがずれる	必ず `l` を先に分割してから `r+1` を分割する
毎回全区間を舐めてO(N)クエリにしてしまう	区間数の増減を意識しない実装	`bisect`で対象区間だけを特定する

次のステップ

発展: クエリに「区間加算」「区間内 $k$ 番目に小さい値」「区間の $x$ 乗の総和 mod $p$」を追加した拡張版（CF896C 型）
次回予告: 永続Trie（Persistent Binary Trie・バージョン管理XOR最大値クエリ）

自己評価

完全理解おおむね理解要復習

Day 098-Q1 — Chtholly Tree（Old Driver Tree・区間代入+区間和）

問題