Codeforces 🎨 CF2179H. Blackslex and Plants

🔗 CF2179H Blackslex and Plants

rating: 2217

Problem Statement

題目大意

有 $n$ 株植物，初始水量為 $0$。
進行 $q$ 次操作，每次給定區間 $[l, r]$，對區間內的第 $i$ 株植物（$l \le i \le r$）增加 $f(i-l+1)$ 的水量。
最後輸出所有植物的水量。

定義 $f(x)$

$f(x) = x \times \text{lowbit}(x)$
其中 $\text{lowbit}(x)$ 為 $x$ 二進位表示中最低位的 $1$ 所代表的值（例如 $\text{lowbit}(6) = \text{lowbit}(110_2) = 2$）。

Constraints

• $1 \le t \le 10^4$
• $1 \le n, q \le 2 \cdot 10^5$
• $\sum n, \sum q \le 2 \cdot 10^5$

---

思路：位元拆解 + 週期性差分陣列

這道題的核心在於函數 $f(x)$ 的性質與區間操作的結合。直接暴力模擬的複雜度是 $O(N \cdot Q)$，無法通過。我們需要利用 lowbit 的特性進行拆解。

1. 數學拆解

我們知道 $\text{lowbit}(x)$ 是 $x$ 二進位表示中最低位的 $1$。假如 $\text{lowbit}(x) = 2^k$，那麼 $x$ 必然同時是 $2^1, 2^2, \dots, 2^k$ 的倍數。
我們可以利用幾何級數 $2^k = 1 + (2^0 + 2^1 + \dots + 2^{k-1})$ 的性質，將 $\text{lowbit}(x)$ 表達成「所有整除 $x$ 的 $2$ 的冪次」的貢獻總和。我們引入 艾佛森括號（Iverson bracket） $[P]$，若條件 $P$ 成立則為 1，否則為 0：

$$\text{lowbit}(x) = 1 + \sum_{j=1}^{\infty} [2^j \mid x] \cdot 2^{j-1}$$

將此代入 $f(x) = x \times \text{lowbit}(x)$：

$$\begin{aligned} f(x) &= x \times \left( 1 + \sum_{j=1}^{\infty} [2^j \mid x] \cdot 2^{j-1} \right) \\ &= \underbrace{x}_{\text{基本層}} + \sum_{j=1}^{\infty} \underbrace{([2^j \mid x] \cdot x) \cdot 2^{j-1}}_{\text{額外層級 } j} \end{aligned}$$

這個公式告訴我們，對於任何一個位置 $i$（對應數值 $x = i - l + 1$），它要加的總水量可以看作是由很多層獨立的規則累加起來的：

• 基本層 ($j=0$)：不管 $x$ 是多少，都要加上 $x \times 1$ 的水。
• 額外層級 1 ($j=1$)：如果 $x$ 是 $2$ 的倍數，額外再加 $x \times 2^0$ 的水。
• 額外層級 2 ($j=2$)：如果 $x$ 是 $4$ 的倍數，額外再加 $x \times 2^1$ 的水。
• 額外層級 $j$ ($j > 2$)：如果 $x$ 是 $2^j$ 的倍數，額外再加 $x \times 2^{j-1}$ 的水。

2. 週期性差分陣列

對於特定層級 $b$ 和區間查詢 $[l, r]$，我們只關心滿足 $(i - l + 1)$ 是 $2^b$ 倍數的位置 $i$。
這些位置 $i$ 構成一個步長 $Step = 2^b$ 的等差數列。

引入週期性差分陣列

若直接遍歷這些位置進行修改，複雜度難以承受。為了在 $O(1)$ 時間內完成對這些「間隔位置」的區間修改，我們引入步長為 $Step$ 的週期性差分陣列（即 diff[i] 與 diff[i+Step] 互為差分關係）。透過在起點與終點標記，即可達成對整段數列的更新。

對於選中的位置 $i$，增加的水量為：

$$\text{Val} = (i - l + 1) \times W_b$$

其中 權重 $W_b$ 為：

$$W_b = \begin{cases} 1 & \text{if } b = 0 \\ 2^{b-1} & \text{if } b \ge 1 \end{cases}$$

展開並將 $W_b$ 提出後：

$$\text{Val} = ( \underbrace{1 \cdot i}_{\text{變數項}} - \underbrace{(l - 1)}_{\text{常數項}} ) \times W_b$$

區間修改策略：
由於增加的水量 $\text{Val}$ 是關於位置 $i$ 的一次函數，單靠一個維護「固定數值」的差分陣列無法滿足需求（因為加的值隨位置 $i$ 改變）。
我們可以將函數拆解為「$i$ 的係數」與「常數項」兩部分，並利用兩個差分陣列分別維護：

1. 維護變數項 ($i$)：使用 diff1 記錄 $i$ 的係數。若標記 diff1 增加 1，則還原後該區間內每個位置 $i$ 的值會增加 $1 \cdot i$。
2. 維護常數項 ($l-1$)：使用 diff2 記錄常數值。若標記 diff2 增加 $(l-1)$，則還原後該區間內每個位置的值會增加 $(l-1)$。

累積兩者的效果並乘上 $W_b$，即為目標增量。

如何 $O(1)$ 計算起點 st 與終點 ed？

我們需要找出區間 $[l, r]$ 內所有滿足 $i - l + 1$ 是 $2^b$ 的倍數的位置。

1. 尋找起點 st：
   第一個滿足條件的點，其相對位置 $i - l + 1$ 必須等於 $2^b$（因為相對位置從 1 開始）。

   $$i - l + 1 = 2^b \implies i = l + 2^b - 1$$

   這就是我們差分更新的起點 st。

2. 區間內有多少個滿足條件的數？
   假設區間內有 $k$ 個滿足條件的位置，則第 $k$ 個位置 $i_k$ 必須滿足 $i_k \le r$。
   第 $k$ 個位置可以表示為：

   $$l + k \cdot 2^b - 1 \le r$$

   移項得：

   $$k \cdot 2^b \le r - l + 1 \implies k \le \frac{r - l + 1}{2^b}$$

   代碼中寫作 k = (r - l + 1) >> b。若計算出 $k=0$，表示區間太短，無須處理。

3. 終點 ed (用於差分抵銷)：
   最後一個滿足條件的位置是 $l + k \cdot 2^b - 1$。
   差分抵銷的位置（即下一個循環點）為：

   $$ed = l + (k+1) \cdot 2^b - 1$$

因為操作位置是跳躍的，所有的差分更新與還原都是基於步長 $2^b$ 進行的。

3. 還原與計算答案

所有操作完成後，對每個層級 $b$ 進行步長 $Step = 2^b$ 的前綴和還原：

$$\text{diff}[b][i] += \text{diff}[b][i - Step]$$

最後每個位置 $i$ 的總水量為所有層級貢獻的總和：

$$\text{ans}[i] = \sum_{b} (\text{diff}_1[b][i] \cdot i - \text{diff}_2[b][i]) \times W_b$$

複雜度分析

• 時間複雜度：$\mathcal{O}((N + Q) \log N)$
  • 每個查詢遍歷 $\log N$ 層，為 $\mathcal{O}(Q \log N)$。
  • 最後還原每層遍歷 $N$ 個位置，為 $\mathcal{O}(N \log N)$。
• 空間複雜度：$\mathcal{O}(N \log N)$
  • 需要 $\mathcal{O}(\log N)$ 個長度為 $N$ 的陣列。

---

Code

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

    B = n.bit_length()
    diff1 = [[0] * (n + 1) for _ in range(B)]
    diff2 = [[0] * (n + 1) for _ in range(B)]

    for _ in range(q):
        l, r = map(int, input().split())
        for b in range(B):
            # 區間內有多少個數是 2^b 的倍數
            # l + k * 2^b - 1 <= r => k <= (r - l + 1) / 2^b
            k = (r - l + 1) >> b
            if k == 0: break
            
            # i − l + 1 = 2^b => i = l + 2^b - 1
            st = l + (1 << b) - 1
            # l + (k+1) * 2^b - 1 > r
            ed = l + ((k + 1) << b) - 1

            diff1[b][st] += 1
            diff2[b][st] += (l - 1)
            if ed <= n:
                diff1[b][ed] -= 1
                diff2[b][ed] -= (l - 1)

    ans = [0] * n
    for b in range(B):
        d = 1 << b
        w = 1 if b == 0 else (1 << (b - 1))
        for i in range(1, n + 1):
            if i >= d:
                diff1[b][i] += diff1[b][i - d]
                diff2[b][i] += diff2[b][i - d]
            ans[i - 1] += (diff1[b][i] * i - diff2[b][i]) * w
    print(*ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

---

寫在最後

PROMPT

這裡什麼都沒有。