AtCoder 🟢 ABC435E Cover query

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC435E Cover query

rating: 1011

Problem Statement

題目簡述

有 $N$ 個格子排成一列，初始全白。
依序進行 $Q$ 次操作，每次給定整數 $L_i, R_i$，將區間 $[L_i, R_i]$ 內的所有格子塗黑（已黑者保持黑）。
每次操作後，請輸出當前仍為白色的格子數量。

Constraints

約束條件

• $1 \leq N \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq N$
• 所有輸入皆為整數。

---

思路：離散化 + Lazy Segment Tree

正難則反：轉換問題目標

題目要求每次操作後輸出白色格子的數量。直接維護變動的白色區間較為困難，因為隨著操作進行，白色部分會被切割得支離破碎，難以有效管理。
相對地，塗黑操作是明確的區間覆蓋。若我們轉而維護目前被塗黑的格子總數（記為 $B$），問題就變得單純許多。每次查詢的答案即為：

$$\text{白色格子數} = N - B$$

核心解法：離散化 + 線段樹

這是一道典型的區間覆蓋問題，但由於 $N$ 高達 $10^9$，無法直接建立長度為 $N$ 的陣列。觀察到操作次數 $Q$ 僅 $2 \times 10^5$，且塗色操作只與給定的端點有關，這提示我們使用 離散化 配合 線段樹（Segment Tree） 來解決。

為什麼可以維護區間？（離散化原理）

染黑操作的本質是區間聯集。顏色的變化（由白變黑）只會發生在查詢區間的邊界處。
我們將所有相關的座標點收集起來：對於每個查詢 $[L_i, R_i]$，將 $L_i$ 和 $R_i+1$ 加入集合。

為什麼要用左閉右開區間 $[L, R+1)$？

使用半開區間的主要好處是：區間邊界不會重疊，使得相鄰區間可以無縫拼接，且長度計算統一為 $R - L$。

舉例說明：
假設有兩個操作：塗黑 $[3, 5]$ 和 $[5, 7]$（共享端點 $5$）。

• 閉區間做法：收集端點 $\{3, 5, 5, 7\} \to \{3, 5, 7\}$。
  • 形成的區間段：$[3, 5]$、$[5, 7]$。
  • 問題：格子 $5$ 同時是前一段的右端點與後一段的左端點，在處理時容易重複計算或需要額外判斷。
• 半開區間做法：將 $[3, 5]$ 轉換為 $[3, 6)$，$[5, 7]$ 轉換為 $[5, 8)$。
  • 收集端點 $\{3, 6, 5, 8\} \to \{3, 5, 6, 8\}$。
  • 形成的區間段：$[3, 5)$、$[5, 6)$、$[6, 8)$，長度分別為 $2, 1, 2$。
  • 每個區間段的邊界不重疊，長度即為端點差，且自動處理了重疊部分。

將收集到的座標排序去重後，得到序列 $X_0 < X_1 < \dots < X_m$。
這些座標點將整個數線切分成了 $m$ 個基本區間 $[X_j, X_{j+1})$。
對於任意一個基本區間，它具有以下關鍵性質：
在任意一次操作中，這個區間要麼完全被包含在塗黑範圍內，要麼完全在範圍外。
因此，我們可以將每個區間 $[X_j, X_{j+1})$ 視為一個不可分割的單元（葉節點），其物理長度固定為 $X_{j+1} - X_j$。

線段樹中維護了哪些資訊？

我們使用 Lazy Segment Tree 來維護離散化後的區間，目標是即時查詢「被染黑的總長度」$B$，答案即為 $N - B$。

節點狀態 $S$ = (black_len, total_width)

欄位	意義	特性
black_len	該區間內已被染黑的長度	動態更新
total_width	該區間的物理總長度	建樹後固定

LazySegTree 介面定義（ACL）

使用 LazySegTree 需定義以下元素：

元素	型別	本題定義	說明
op(a, b)	$S \times S \to S$	$(b_1+b_2,\; w_1+w_2)$	合併兩個子區間狀態
e	$S$	$(0, 0)$	狀態單位元素
mapping(f, s)	$F \times S \to S$	$(w, w)$ if $f=1$ else $(b, w)$	Tag 作用於狀態
composition(f, g)	$F \times F \to F$	$f \lor g$	Tag 合成
id	$F$	$0$	Tag 單位元素（無操作）

註：一旦染黑就不會變回白，重複染黑也不會有額外效果，故 Tag 合成使用位元 OR。

Tag 傳遞機制

當執行 apply(L, R, 1) 時：

1. 向下遞迴，對完全被包含的節點打上 Tag $1$，並透過 mapping 更新狀態
2. 後續操作若需進入已標記節點的子樹，先 push_down（下傳 Tag 給子節點）
3. 回溯時透過 op 重新計算父節點狀態

執行流程

1. 離散化：收集所有 $L_i$ 和 $R_i+1$，排序去重建立映射 mapX
2. 建樹：葉節點初始狀態為 $(0, X_{j+1} - X_j)$
3. 處理查詢：seg.apply(mapX[L], mapX[R+1], 1) → 輸出 $N - B = N - \text{seg.all\_prod()}[0]$

複雜度分析

• 時間複雜度：$\mathcal{O}(Q \log Q)$
  • 離散化需排序座標，而座標的數量最多為 $2Q$，耗時 $\mathcal{O}(Q \log Q)$。
  • 線段樹節點數最多 $2Q$，建樹 $\mathcal{O}(Q)$。
  • 每次查詢進行區間更新，耗時 $\mathcal{O}(\log Q)$，總共 $\mathcal{O}(Q \log Q)$。
• 空間複雜度：$\mathcal{O}(Q)$
  • 需儲存離散化座標及線段樹結構。

---

Code

from itertools import pairwise
from atcoder.lazysegtree import LazySegTree

def solve():
    n, q = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(q)]

    Xs = set()
    for l, r in queries:  # [l, r] -> [l, r + 1)
        Xs.add(l)
        Xs.add(r + 1)
    
    Xs = sorted(Xs)
    mapX = {val: i for i, val in enumerate(Xs)}
    data = [(0, y - x) for x, y in pairwise(Xs)]  # (count, length)

    op = lambda a, b: (a[0] + b[0], a[1] + b[1])
    mapping = lambda f, s: (s[1], s[1]) if f == 1 else s
    composition = lambda f, g: f | g
    seg = LazySegTree(op, (0, 0), mapping, composition, 0, data)

    for l, r in queries:
        L, R = mapX[l], mapX[r + 1]
        seg.apply(L, R, 1)
        print(n - seg.all_prod()[0])

if __name__ == '__main__':
    solve()

---

寫在最後

PROMPT

這裡什麼都沒有。