Codeforces #56 E Domino Principle

題意﹕給定 $N$ 個多米諾/骨牌，每個骨牌皆有不同的位置 $X_1 \cdots X_N$ 和高度 $H_1 \cdots H_N$ 。若推倒第 $i$ 個骨牌則 $X_i+1$ 至 $X_i+H_i-1$ 以內的所有骨牌皆會倒下。問每塊骨牌可推倒多少個骨牌(包括自己)。 $1 \le N \le 10^5$ , $-10^8 \le X_i \le 10^8$ 和 $2 \le H_i \le 10^8$ 。

做法當然不能 $O(N^2)$ 枚舉吧。不過先假設 $X_1 < X_2 \cdots < X_N$ ，定義要求答案為 $f_i$ 。設 $c_i = j$ 使得 $X_i + H_i - 1 \le X_j, j > i$ ，即第 $i$ 個骨牌可以接觸到最遠哪個骨牌，如果遇上任何不能推倒的骨牌則表示為 $c_i = \infty$ 。則 $f_i$ 有如下關係﹕


$$f_i = \begin{cases} \max_{i+1\le k\le c_i}\{f_k + k - i\} & \text{if } c_i \ne \infty \\ 1 & \text{otherwise} \end{cases}$$


首先，對於任意 $i$ ，查找 $c_i$ 的方法可以用二分搜索。至於計算 $f_i$ ，我們考慮 $c_i \ne \infty$ 的情況。經簡化可得



$$f_i = \max_{i+1\le k\le c_i}\{f_k + k - i\} = \max_{i+1\le k\le c_i}\{f_k + k\} - i$$


設 $g_k = f_k + k$ 。即，我們從範圍 $i+1$ 至 $c_i$ 之間搜索最大的 $g_k$ 值，這就可以用線段樹輕鬆搞定了。算好 $f_i = \max_k\{g_k\} - i$ 後記得為線段樹的區間 $[i, i]$ 插入數值 $g_i = f_i + i$ 。

說來湊巧，最近與Gagguy聊天起他提起類似問題的做法，之後再做題就剛好遇上此題，所以推導公式還是比較便捷，在此先行感謝Gagguy指點。