問題
長さ $N$ の配列 $A$ が初期値 $0$ で与えられる。$Q$ 個のクエリを処理せよ。
- クエリ型 1:
1 l r c— $A[l..r)$ をすべて $c$ に変更する。 - クエリ型 2:
2 l r— 区間 $[l, r)$ 内の隣接する異なる値の境界数（$\sum_{i=l}^{r-2} [A[i] \neq A[i+1]]$）を出力せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 2 \times 10^5$ |
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
| $l, r$ | $0 \le l < r \le N$ |
| $c$ | $1 \le c \le 10^9$ |
入出力例
入力例 1
8 5
1 0 8 1
2 0 8
1 2 6 2
1 5 8 3
2 0 8出力例 1
0
3変更後: [1,1,2,2,2,3,3,3] → インデックス1→2, 4→5 の2箇所… 実際は境界が3箇所。
概念図: 遅延セグメント木のノード設計
ヒント（段階的開示）
ヒント1: 方向性
遅延セグメント木で区間 Assign（一括上書き）を管理しつつ、各ノードに「区間内の色変化数」「左端値」「右端値」を持たせる。
ヒント2: アプローチ
各ノードに保持する情報:
lv: 区間の一番左の値rv: 区間の一番右の値cnt: 区間内の隣接色変化数lazy: -1=なし、それ以外=一括上書き値
マージ: 左子の rv と右子の lv が異なれば cnt が +1。
ヒント3: コード骨格
class Node:
def __init__(self):
self.lv = self.rv = 0
self.cnt = 0
self.lazy = -1
def merge(l, r):
node = Node()
node.lv = l.lv
node.rv = r.rv
node.cnt = l.cnt + r.cnt + (1 if l.rv != r.lv else 0)
return node模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
N, Q = map(int, input().split())
size = 1
while size < N:
size <<= 1
lv = [0] * (2 * size)
rv = [0] * (2 * size)
cnt = [0] * (2 * size)
lazy = [-1] * (2 * size)
def push_down(k):
if lazy[k] != -1:
v = lazy[k]
for c in [2*k, 2*k+1]:
lv[c] = rv[c] = v
cnt[c] = 0
lazy[c] = v
lazy[k] = -1
def pull_up(k):
lv[k] = lv[2*k]
rv[k] = rv[2*k+1]
cnt[k] = cnt[2*k] + cnt[2*k+1] + (1 if rv[2*k] != lv[2*k+1] else 0)
def update(k, node_l, node_r, ql, qr, v):
if qr <= node_l or node_r <= ql:
return
if ql <= node_l and node_r <= qr:
lv[k] = rv[k] = v
cnt[k] = 0
lazy[k] = v
return
push_down(k)
mid = (node_l + node_r) // 2
update(2*k, node_l, mid, ql, qr, v)
update(2*k+1, mid, node_r, ql, qr, v)
pull_up(k)
def query(k, node_l, node_r, ql, qr):
if qr <= node_l or node_r <= ql:
return None
if ql <= node_l and node_r <= qr:
return (lv[k], rv[k], cnt[k])
push_down(k)
mid = (node_l + node_r) // 2
L = query(2*k, node_l, mid, ql, qr)
R = query(2*k+1, mid, node_r, ql, qr)
if L is None: return R
if R is None: return L
return (L[0], R[1], L[2] + R[2] + (1 if L[1] != R[0] else 0))
out = []
for _ in range(Q):
line = list(map(int, input().split()))
if line[0] == 1:
_, l, r, c = line
update(1, 0, size, l, r, c)
else:
_, l, r = line
res = query(1, 0, size, l, r)
out.append(res[2] if res else 0)
print('\n'.join(map(str, out)))
main()Step-by-Step 解説
Step 1: ノード設計
各ノードは区間の「左端値・右端値・変化数・lazy」を保持する。区間 Assign では全要素が同一値になるので cnt=0, lv=rv=v。
Step 2: マージ操作
左子の右端値と右子の左端値が異なるとき、境界で +1 の変化が生じる。
Step 3: クエリ（型2）
クエリ区間にまたがる複数のノードをマージしていく。左端・右端・変化数を伝播させながら結合する。
Step 4: 計算量
| 操作 | 計算量 |
|---|---|
| Update（区間 Assign） | $O(\log N)$ |
| Query（区間変化数） | $O(\log N)$ |
| 全体 | $O((N + Q) \log N)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| マージ時に境界チェックを忘れる | lv_right == rv_left の場合は加算しない | cnt += 1 if lv_right != rv_left else 0 |
| lazy適用後にpull_upしない | pull_upを呼ばないと祖先ノードが不整合 | update後に必ずpull_up |
| queryで区間外ノードのlv/rvを混入 | Noneチェック不足 | L/Rがいずれかの場合の処理を追加 |
次のステップ
発展問題: 区間 Assign + 区間 Add の複合遅延伝播（beats + 通常lazy）。関連: Chtholly Tree（区間一様値の集合管理）による同等問題の別解。