AtCoder 🔵 ABC428F Pyramid Alignment

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

🔗 🔵 ABC428F Pyramid Alignment

Problem Statement

題目簡述

在數線上給定 $N$ 個區間，一開始第 $i$ 個區間為 $[0, W_i]$，且 $W_1 < W_2 < \dots < W_N$。
給定 $Q$ 次操作，有三種類型：

1. 1 v：將編號 $1 \sim v$ 的所有區間平移，使其左端點對齊目前第 $v$ 個區間的左端點。
2. 2 v：將編號 $1 \sim v$ 的所有區間平移，使其右端點對齊目前第 $v$ 個區間的右端點。
3. 3 x：詢問目前共有多少個區間包含座標點 $x+\frac{1}{2}$。

Constraints

約束條件

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq W_i \leq 10^9$
• $W_1 < W_2 < \dots < W_N$
• $1 \le v \le N$
• $0 \le x \le 10^9$

---

思路：Lazy Segment Tree

核心觀察：區間永遠維持「巢狀」

這題真正的核心不是一開始就想到 Lazy SegTree，而是需要先發覺一個非常強的結構性質：任何時刻都會有

$$[L_1,R_1] \subseteq [L_2,R_2] \subseteq \cdots \subseteq [L_N,R_N]$$

也就是編號越大，區間越大，永遠是一層包一層。

1. 為什麼一直保持巢狀？

1. 初始狀態：一開始都是左端點 $0$，而且 $W_i$ 嚴格遞增，所以顯然 $[0,W_1] \subseteq [0,W_2] \subseteq \cdots \subseteq [0,W_N]$。
2. 操作 1（左端點對齊）：把前綴 $(1\sim v)$ 的左端點全部改成同一個 $L_v$。
   • 前綴變成：$[L_v, L_v+W_1], [L_v, L_v+W_2], \dots, [L_v, L_v+W_v]$
   • 因為長度 $W_i$ 遞增，所以右端點也遞增，前綴內部仍然是巢狀。
   • 而第 $v$ 條區間本身沒變，原本就是被第 $v+1$ 條包含，所以整體巢狀不變。
3. 操作 2（右端點對齊）：把前綴 $(1\sim v)$ 的右端點全部改成同一個 $R_v$。
   • 前綴變成：$[R_v-W_1, R_v], [R_v-W_2, R_v], \dots, [R_v-W_v, R_v]$
   • 因為 $W_i$ 遞增，左端點 $R_v-W_i$ 會越來越小，所以一樣是巢狀。

2. 巢狀性質如何簡化詢問 3？

若所有區間都是巢狀，對任意一個查詢點 $p = x+\frac{1}{2}$：

• 前面小區間可能不包含它
• 一旦某個區間開始包含，後面所有更大的區間一定都包含

結論：答案必為一個後綴

包含 $x+\frac{1}{2}$ 的區間分佈形如 0, 0, 0, 1, 1, 1, 1。因此，問題退化成：找到第一條「包含 $x+\frac{1}{2}$」的區間位置 $r$，那麼答案就是 $N-r$。

另外，因為區間端點都是整數，包含判斷可以完全免除浮點數：

• $L \le x + \frac{1}{2} \le R \iff L \le x \text{ 且 } R \ge x+1$
• 反之，「不包含」就是：$L > x \text{ 或 } R < x+1$。

3. 線段樹的節點與延遲標記設計

理解了上面性質後，我們只需要用資料結構來處理這兩種「區間端點修改」的操作，因為只需查詢前綴/後綴屬性，用 Lazy Segment Tree 再適合不過。

節點 S 到底要記錄什麼？

一個區間節點所代表的 prefix，如果它最右邊那一條區間都不包含點，那整個 prefix 肯定全不包含（巢狀）；如果最右邊那一條已經包含了，就表示邊界出現了。所以對於任意一個連續區段，只要存該段「最右邊的那個元素」的資訊即可。

於是，節點狀態宣告為 (sz, lr, wr)：

• sz：這段合併的區間數量。
• lr：這段區間中，最右端那個元素的左端點。
• wr：這段區間中，最右端那個元素的固定長度 $W$。

op 的合併邏輯：
因為我們只關注最右邊元素的資訊，合併兩段（左段 $a$、右段 $b$）時，直接取右段的最右邊資訊，並將長度相加：(sz_a + sz_b, lr_b, wr_b)。

F 標記的設計：
雖然操作 1 和 2 是對齊左/右端點，但若都轉換為「這條區間的左端點變成多少」，邏輯會更好統一：

• (mode=1, c)：左對齊。所有左端點直接賦值為 $c$。也就是 $L \gets c$。
• (mode=2, c)：右對齊。所有右端點對齊為 $c$，等價於左端點 $L \gets c - W$。

mapping (套用標記)：
當把標記套用至狀態時，由於我們只記錄了最右邊的元素，且該元素長度為 $wr$：

• 若 mode == 1：回傳新的左端點 $c$，總長度 $wr$ 不變。
• 若 mode == 2：回傳新的左端點 $c - wr$，總長度 $wr$ 不變。

composition (標記合成)：
這兩種更新本質都是「直接賦值整段重新計算」，不是加法或疊加，所以如果有新操作 $f$，它會直接覆蓋舊操作 $g$。

4. 透過 max_right 找出答案

查詢 3 x 給定點 $x+\frac{1}{2}$，我們可以套用 ACL 線段樹內建的 seg.max_right(0, check)。
這會找最大的 $r$，使得前綴 $[0, r)$ 皆滿足 check 條件。我們的條件是：這條區間不包含 $x+\frac{1}{2}$。

def check(s):
    _, lr, wr = s
    return not (lr <= x and x + 1 <= lr + wr)

這樣 max_right 回傳的 $r$，它的意義就是第一條包含目標點的區間下標。答案即為後綴長度 $N - r$。
（這正對應程式中的 not (lr <= x and x + 1 <= lr + wr) 即為 lr > x or lr + wr < x + 1。）

複雜度分析

• 時間複雜度：
  • 初始化線段樹 $\mathcal{O}(N)$
  • 每次操作：修改前綴區間或使用 max_right 二分搜皆為 $\mathcal{O}(\log N)$
  • 總時間複雜度 $\mathcal{O}((N + Q) \log N)$
• 空間複雜度：線段樹所需的節點陣列大小 $\mathcal{O}(N)$

---

Code

from atcoder.lazysegtree import LazySegTree


def solve():
    n = int(input())
    W = list(map(int, input().split()))

    # S = (sz, lr, wr)
    # sz : 包含的元素(區間)個數
    # lr : 最右端元素對應區間的左端點
    # wr : 最右端元素對應區間的長度
    e = (0, 0, 0)

    def op(a, b):
        sz_a, lr_a, wr_a = a
        sz_b, lr_b, wr_b = b
        if sz_b == 0:
            return a
        return (sz_a + sz_b, lr_b, wr_b)

    # F = (mode, c)
    # mode = 1  : L <- c
    # mode = 2  : L <- c - W
    id_ = (0, 0)

    def mapping(f, s):
        mode, c = f
        sz, lr, wr = s
        if sz == 0 or mode == 0:
            return s
        return (sz, c if mode == 1 else c - wr, wr)

    def composition(f, g):
        # 新操作 f 蓋掉舊操作 g
        return f if f[0] else g

    data = [(1, 0, w) for w in W]
    seg = LazySegTree(op, e, mapping, composition, id_, data)

    ans = []

    q = int(input())
    for _ in range(q):
        t, *args = map(int, input().split())

        if t == 1:
            v = args[0] - 1
            lv = seg.get(v)[1]
            seg.apply(0, v + 1, (1, lv))  # apply to [0, v + 1)
        elif t == 2:
            v = args[0] - 1
            lv = seg.get(v)[1]
            rv = lv + W[v]
            seg.apply(0, v + 1, (2, rv))
        else:
            x = args[0]

            # 找到第一個包含 x + 0.5 的區間位置
            def check(s):
                _, lr, wr = s
                return not (lr <= x and x + 1 <= lr + wr)

            r = seg.max_right(0, check)
            ans.append(n - r)  # [r, n) 對應的區間皆包含 x + 0.5

    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()