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

🔗 ABC437F Manhattan Christmas Tree 2

rating: 1305

Problem Statement

題意簡述

平面上有 NN 棵聖誕樹，第 ii 棵樹位於 (Xi,Yi)(X_i, Y_i)。
需依序處理 QQ 個詢問：

  • Type 1 (1 i x y)：將第 ii 棵樹的座標變更為 (x,y)(x, y)。
  • Type 2 (2 L R x y)：計算點 (x,y)(x, y) 到第 L,L+1,…,RL, L+1, \ldots, R 棵樹中，最遠的曼哈頓距離 (Manhattan Distance)。
曼哈頓距離 (Manhattan Distance)

其中曼哈頓距離定義為 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|。

Constraints

約束條件

  • 1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5
  • −109≤Xi,Yi,x,y≤109-10^9 \le X_i, Y_i, x, y \le 10^9

思路：曼哈頓距離轉切比雪夫距離 + 線段樹

這是一道經典的 曼哈頓距離 (Manhattan Distance) 處理問題。題目要求在動態修改點座標的情況下，查詢一段區間內的點到給定點的最大曼哈頓距離。

核心轉換

曼哈頓距離 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2| 涉及絕對值，我們可以根據 x1−x2x_1 - x_2 與 y1−y2y_1 - y_2 的符號關係來拆解。

令 A=x1−x2A = x_1 - x_2，B=y1−y2B = y_1 - y_2。

  • 若 A,BA, B 同號（同正或同負），則 ∣A∣+∣B∣=∣A+B∣|A| + |B| = |A+B|。
  • 若 A,BA, B 異號，則 ∣A∣+∣B∣=∣A−B∣|A| + |B| = |A-B|。

綜合這兩種情況，我們可以得到恆等式：∣A∣+∣B∣=max⁡(∣A+B∣,∣A−B∣)|A| + |B| = \max(|A+B|, |A-B|)。
將 A,BA, B 代回原式並整理：

∣x1−x2∣+∣y1−y2∣=max⁡(∣(x1−x2)+(y1−y2)∣,∣(x1−x2)−(y1−y2)∣)=max⁡(∣(x1+y1)−(x2+y2)∣,∣(x1−y1)−(x2−y2)∣)\begin{aligned} |x_1 - x_2| + |y_1 - y_2| &= \max(|(x_1 - x_2) + (y_1 - y_2)|, |(x_1 - x_2) - (y_1 - y_2)|) \\ &= \max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_1) - (x_2 - y_2)|) \end{aligned}

幾何意義

事實上，這正好是兩點在座標轉換 (u,v)=(x+y,x−y)(u, v) = (x+y, x-y) 後的 切比雪夫距離 (Chebyshev Distance)。

為了方便，我們定義每個點 ii 的兩個特徵值：

  • Si=Xi+YiS_i = X_i + Y_i (Sum)
  • Di=Xi−YiD_i = X_i - Y_i (Difference)

那麼點 (Xi,Yi)(X_i, Y_i) 與查詢點 (x,y)(x, y) 的曼哈頓距離可以表示為：

disti=max⁡(∣Si−(x+y)∣,∣Di−(x−y)∣)\text{dist}_i = \max(|S_i - (x+y)|, |D_i - (x-y)|)

去除絕對值

我們要查詢的是區間 [L,R][L, R] 內所有 ii 的最大距離。對於固定的查詢點 (x,y)(x, y)，上式中的絕對值可以拆解為四種情況取最大值：

  1. Si−(x+y)S_i - (x+y)
  2. (x+y)−Si(x+y) - S_i
  3. Di−(x−y)D_i - (x-y)
  4. (x−y)−Di(x-y) - D_i

也就是說，對於區間查詢，我們只需要找到區間 [L,R][L, R] 內的：

  • max⁡(Si)\max(S_i)
  • min⁡(Si)\min(S_i)
  • max⁡(Di)\max(D_i)
  • min⁡(Di)\min(D_i)

只要維護這四個數值，答案即為：

max⁡{max⁡(Si)−(x+y)(x+y)−min⁡(Si)max⁡(Di)−(x−y)(x−y)−min⁡(Di)\max \begin{cases} \max(S_i) - (x+y) \\ (x+y) - \min(S_i) \\ \max(D_i) - (x-y) \\ (x-y) - \min(D_i) \end{cases}

資料結構選擇

由於需要支援 單點修改 (Type 1) 與 區間最值查詢 (Type 2)，我們可以使用 線段樹 (Segment Tree)。

具體來說，我們需要建立 4 棵線段樹（或是 1 棵維護 4 個值的線段樹）：

  1. seg1: 維護區間 SiS_i 的最大值
  2. seg2: 維護區間 SiS_i 的最小值
  3. seg3: 維護區間 DiD_i 的最大值
  4. seg4: 維護區間 DiD_i 的最小值
實作細節

使用 AtCoder Python Library (ACL) 的 segtree 可以很方便地實作。

  • op 函數分別設為 max 和 min。
  • e (單位元) 分別設為 float('-inf') 和 float('inf')。

複雜度分析

  • 時間複雜度：O(Qlog⁡N)\mathcal{O}(Q \log N)
    • 建樹：O(N)\mathcal{O}(N)
    • 每次更新 (Type 1)：O(log⁡N)\mathcal{O}(\log N)
    • 每次查詢 (Type 2)：O(log⁡N)\mathcal{O}(\log N)
  • 空間複雜度：O(N)\mathcal{O}(N) (用於存儲線段樹)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from atcoder.segtree import SegTree

fmax = lambda a, b : a if a > b else b
fmin = lambda a, b : a if a < b else b

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

    seg1 = SegTree(fmax, float('-inf'), [x + y for x, y in P])
    seg2 = SegTree(fmin, float('inf'), [x + y for x, y in P])
    seg3 = SegTree(fmax, float('-inf'), [x - y for x, y in P])
    seg4 = SegTree(fmin, float('inf'), [x - y for x, y in P])

    for _ in range(q):
        op, *args = map(int, input().split())
        if op == 1:
            i, x, y = args
            seg1.set(i - 1, x + y)
            seg2.set(i - 1, x + y)
            seg3.set(i - 1, x - y)
            seg4.set(i - 1, x - y)
        else:
            l, r, x, y = args
            max_s = seg1.prod(l - 1, r)
            min_s = seg2.prod(l - 1, r)
            max_d = seg3.prod(l - 1, r)
            min_d = seg4.prod(l - 1, r)
            
            print(max(max_s - (x + y), (x + y) - min_s, max_d - (x - y), (x - y) - min_d))

if __name__ == "__main__":
    solve()

寫在最後

PROMPT

這裡什麼都沒有。