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

🔗 🌈 AWC0104D Radio Tower and Receiver

Problem Statement

題目簡述

有 NN 個排成一直線的位置，每個位置 ii 有容許值 TiT_i。共有 MM 座基地台，第 jj 座位於 PjP_j，強度為 BjB_j。

若某位置到基地台的接收強度 Bj−∣i−Pj∣B_j-|i-P_j| 為正，該基地台會對此位置產生這個值的貢獻；否則沒有貢獻。令 SiS_i 為位置 ii 收到的總強度，要求在所有滿足 Si≤TiS_i\le T_i 的位置中，找出最大的 SiS_i。

Constraints

約束條件

  • 1≤N≤2×1051\le N\le 2\times 10^5
  • 1≤M≤2×1051\le M\le 2\times 10^5
  • 1≤Ti≤10141\le T_i\le 10^{14}
  • 1≤Pj≤N1\le P_j\le N
  • 1≤Bj≤N1\le B_j\le N
  • 保證至少存在一個位置可以讓接收器正常運作。
  • 所有輸入皆為整數。

思路：等差數列差分

先看題目本質。對於一座位於中心位置、強度為 BB 的基地台，它對左右兩側的貢獻不是任意形狀，而是一個「三角形」：中心位置貢獻 BB，往左或往右每走一步就少 11，直到不再為正為止。

也就是說，每座基地台其實是在總強度陣列上加上兩段等差數列：

  • 左半邊：從影響範圍左端一路遞增到中心，公差為 11。
  • 右半邊：從中心右側一路遞減到影響範圍右端，公差為 −1-1。

如果逐座基地台、逐個位置累加，最壞會退化成 O(NM)\mathcal{O}(NM)，無法通過 2×1052\times 10^5 的資料範圍。既然每次加的都是等差數列，就應該想辦法一次標記整段，而不是逐項累加。

從普通差分到等差數列差分

回顧普通差分：對區間加上常數 vv，只需要在差分陣列的左端點加 vv、右端點後一個位置減 vv，最後做一次前綴和就能還原。

現在要加的不是常數，而是一段等差數列。先看加入後，一階差分陣列會變成什麼樣子。以長度為 44 的區間 [l,r][l,r] 為例，若加上

s, s+d, s+2d, s+3ds,\ s+d,\ s+2d,\ s+3d

令末項 e=s+3de=s+3d。原序列、一階差分，以及在一階差分上再做一次差分（二階差分）的變化如下：

位置 ll l+1l+1 l+2l+2 l+3=rl+3=r r+1r+1 r+2r+2
原序列 ss s+ds+d s+2ds+2d ee 00 00
一階差分 ss dd dd dd −e-e 00
二階差分 ss d−sd-s 00 00 −d−e-d-e ee
關鍵觀察

一階差分的中間段全部是 dd，也就是一段常數。既然一階差分上出現常數段，就可以再做一次差分，也就是在一階差分陣列上繼續差分，得到二階差分。

這樣一來，原本在一階差分上的常數段 dd，到了二階差分就全部歸零，只剩下四個端點需要標記。

因此，若要在 [l,r][l,r] 加入首項為 ss、公差為 dd 的等差數列，設末項為

e=s+(r−l)de=s+(r-l)d

只要做以下四個端點更新：

Dl+=sDl+1+=d−sDr+1+=−d−eDr+2+=e\begin{aligned} D_l &\mathrel{+}= s\\ D_{l+1} &\mathrel{+}= d-s\\ D_{r+1} &\mathrel{+}= -d-e\\ D_{r+2} &\mathrel{+}= e \end{aligned}

最後對這個二階差分陣列做兩次前綴和，就能還原所有位置的總接收強度。

核心套路：二階差分

對一階差分陣列再做差分，可以把「區間加等差數列」壓縮成四個端點更新，再透過兩次前綴和還原。這個技巧俗稱「等差數列差分」。

常見陷阱

拆成左右兩段時，中心只能算一次。這份實作把中心放在左半邊，右半邊從中心右側開始。

正確性說明

對任一座基地台，它對每個位置的正貢獻恰好由左半邊遞增等差數列與右半邊遞減等差數列組成，兩段合起來不重不漏地覆蓋所有接收強度為正的位置。

等差數列差分的四個端點更新，經過兩次前綴和後會在指定區間還原出首項為 ss、公差為 dd 的等差數列，區間外貢獻為 00。因此，對所有基地台做這些更新後，線性還原得到的值就是每個位置收到的總強度 SiS_i。

最後掃描所有位置，只在 Si≤TiS_i\le T_i 時更新答案，所以輸出的正是所有可正常運作位置中的最大總接收強度。

複雜度分析

  • 時間複雜度：O(N+M)\mathcal{O}(N+M)
  • 空間複雜度：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
35
36
37
38
39
40
def solve():
    n, m = map(int, input().split())
    T = list(map(int, input().split()))
    P, B = [], []
    for _ in range(m):
        p, b = map(int, input().split())
        P.append(p - 1)
        B.append(b)
    assert len(T) == n and len(P) == m and len(B) == m

    # 等差數列差分
    diff = [0] * (n + 2)

    def add(l, r, s, d):
        if l > r:
            return
        e = s + (r - l) * d
        diff[l] += s
        diff[l + 1] += d - s
        diff[r + 1] += -d - e
        diff[r + 2] += e

    for p, b in zip(P, B):
        l = max(p - b, 0)
        add(l, p, b - (p - l), 1)
        r = min(p + b, n - 1)
        add(p + 1, r, b - 1, -1)

    ans = 0
    s = ss = 0
    for i, t in enumerate(T):
        s += diff[i]
        ss += s
        if ss <= t:
            ans = max(ans, ss)
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Rosuuri. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.