Codeforces #78

題目出乎意料之外的難…

A: 給定三行字串 $s_1, s_2, s_3$ 問其帶母音數是否等於 $(5, 7, 5)$ 。送分題。

B: 現在有 $7 \le N \le 100$ 個人圍成一圈，現在要分派7種顏色的復活蛋，要求是每種顏色的復活蛋必須至少有一人被分發，而且任意連續四人分配到的必須是四種不同顏色的蛋。給出一種可能分發復活蛋的方案。

先把顏色變成數字 $[1, 7]$ 。因為題目保証答案永遠存在，不妨先考慮 $N = 8$ 的情況。如果第1至7人分別得到顏色為 $1, 2, \cdots 7$ 的復活蛋的話，哪麼第8人應該拿甚麼顏色？注意第一個條件已經滿足了，要讓第二條件滿足，關鍵在如何分配給第8個人。若過他往前看3人拿的顏色，應是 $\{1, 2, 3\}$ ；往後看的話則是 $\{5, 6, 7\}$ ，故他只能取得顏色為 $[1, 7] - \{1, 2, 3, 5, 6, 7\} = \{4\}$ 的蛋。若是第9人呢？首先按同樣道理往前看已決定他不能取顏色為 $\{1, 2, 3\}$ 的復活蛋，但往後看的話現在則不能拿到 $\{4, 6, 7\}$ 的蛋，故只剩下顏色為5的蛋可取。注意往前再分析第8人時它本來向前看的顏色是 $\{1, 2, 3\}$ 現在變成了 $\{5, 1, 2\}$ 但條件仍舊滿足。細心再推論之下其實派蛋的方法是遵從這種數列﹕ $(1, 2, 3, 4, 5, 6, 7, 4, 5, 6, 7, 4, 5, 6, 7, 4, 5, 6, 7\cdots)$ 。

C: 問有 $N$ 條木棒，各長度皆為 $M$ 。現在兩人輪流玩遊戲。每一回合其中一人必須選擇一根木棒，折成多於一條均等整數長度的木棒，且其長度不得少於 $K$ 。沒法進行此一操作者為負方。現給定 $N, M, K$ 決定誰是勝方。

二人博弈問題。先不想 $M, K$ 的，考慮 $N$ 對賽局的影響。把木棒分成一雙雙，可以發現如果 $N$ 是偶數的話當先手選擇某一雙的一根木棒毅行操作，對方可選該雙的另一根木棒進行同樣的操作，因此先手必負。如果 $N$ 是奇數的話，根據同樣道理可知先手最後被迫對剩下的一根長度為 $M$ 的木棒進行操作。

因此遊戲在 $N$ 是奇數的情況下可以視作只有一根木棒的遊戲。同樣對 $N$ 為偶數的特性，先手必須盡量把木棒分成雙數等分的木棒，且長度至少為 $K$ ，此舉可以讓對方陷入必敗局。若不存在這樣的一步，則直接看看能否把木棒分拆即可。因為通過分拆成剛好大於 $K$ 的木棒後對方必不能再進行操作，因此能找到這樣的分拆必也可以直接勝出。需要注意 $N = K = 1$ 的情況： $M = 1$ 時必敗， $M > 1$ 時必勝。

D: 簡單點說就是問一個以邊長為1的正六邊形舖密的蜂巢狀世界，假設你站在其中一個正六邊形的中點為座標的原點，視野是一半徑為 $R$ 的圓，問有多少個半正六邊形是被這圓所包含的？包含的定義是指該正六邊形內任意一點必須與原點距離少於等於 $R$ 。下圖展示了 $R = 6$ 所包含的31個正六邊形﹕



紅線是視野，橙色的正六邊形是被包含的正六邊形。
做法是考慮圓形上的一個象限，如下圖﹕



然後沿著從象限左至右 $O(1)$ 求新一個直行能最盡延伸的正六邊形，如下圖﹕



利用上下對稱原理可計算該直行有多少個被包含的正六邊形，因此半個圓的答案 $S$ 可以快速求得。然後再用左右對稱的原計算答案 $C = 2S - S_1$ 當中 $S_1$ 是中心那個直行包含了多少個正六邊形，因為 $2S$ 重覆計算了該行的數量。

注意﹕枚舉移動格子的時候不應用加法更新縱座標，因為對於 $N$ 較大的時候，加法更新會引致精度問題﹕如果能重新計算距離的話則可以防止精度問題發生。

[更新]所謂的重新計算是基於對格子進行標號，如下圖﹕


那麼對於偶數直行的縱座標即是 $L_y \times \sqrt{3}$ ，奇數行的則是 $L_y \times \sqrt{3} + \frac{\sqrt{3}}{2}$ 。

E: 給了一個 $N\times N$ 的地圖。每個格子要麼是一個房間，要麼是一個毒氣罐且佔滿整個格子。現在某些毒氣罐洩漏了毒氣，每一時間單位向鄰接格子擴散。最初每個房間含最多9人，每個房間含逃生倉最多9個。人們以每一個時間單位向鄰接房間移動，如在該房間內遇上未佔用的逃生倉即可進內並不受毒氣毒害。退化情況下，如毒氣和人員能在同一時間內到達未佔用逃生倉的房間，則該人亦能佔用逃生倉而不受毒氣侵害。更糟糕的時，整個地方會在剛好 $t$ 個時間單位後發生大爆炸，幸運的是逃生倉內的人亦不受損害。求最多有多少人在 $t$ 秒後仍然生存。

先不考慮毒氣的擴散，問題就是某些地方有人，某些地方有逃生倉，求 $t$ 步內可以滿足最多生存人數。不難留意 $N \times N$ 的地圖等價於格網圖，先設為 $G$ ，如下圖所示﹕


現在問題即是求限制 $t$ 步的最大流，其中 $t$ 步限制即可以利用層圖解決。做法是把 $G$ 複製成 $t+1$ 份 $G_0, G_1, \cdots G_t$，如下圖﹕



然後把 $G_t$ 的所有邊移去，對於 $0 \le i < t$ ， $G_i$ 的邊 $(u_i, v_i)$ 變成 $(u_i, v_{i+1})$ 。那麼上述例子的圖大概會變成下圖﹕



然後把源點 $s$ 連上 $G_0$ 上的所有點，並設容量為最初地圖上的人員數。對於帶逃生倉的點 $v \in G$ ，把 $v_i$ 連上局部匯 $t_v$ 並設容量為逃生倉的數量。最後把所有 $t_v$ 連上匯 $t$ ，同樣設容量為逃生倉的數量。最大流即可求得答案。

如果加上毒氣的話怎麼辦？首先是依毒氣的流動計算 $G$ 任何一個點 $v$ 至少甚麼時候會被毒氣侵襲(設為 $\infty$ 或 $t+1$ 即代表不受影響)，設該數值為 $L_v$ 。然後對於所有 $G_i, i \le L_v$ 把點 $v_i$ 的所有邊都移除即可。

至於本題的最大流應該用甚麼算法去解決，先考慮點的數量。用層圖的方法最多有 $(t+2)N^2 + N + 2$ 。因為 $t \le 60, N \le 10$ ，點的數量最多可達 $6212$ 個。但留意此層圖非常稀疏，因此粗略計算，邊的數量最多為 $6(t+1)N^2 + N$ ，仍是線性數量的。而且答案最大為 $9\times 10^2 = 900$ ，因此用Ford-Fulkerson算法，於 $O(Ef)$ 的複雜度下運行時間仍然讓人滿意。

Codeforces #26 D Tickets

題意﹕現在有一個計數器，數值最初為 $k$ ，並有兩個按鈕﹕一是可以讓計數器加一，一是可以讓計數器減一。現在你可以按 $n$ 次加一 $m$ 次減一，若你選取操作的排例的概率是均等，那麼有多少機會使得你在操作中途計數器總是非負？

首先，用圖表的方式去想。假定橫軸是操作的時序，縱軸代表計數器在某個時刻的數值，那麼一個操作順序剛好表示了一副折線圖。像如下的圖代表操作不會引致負數﹕



順道留意﹕終點永遠在座標 $(n+m, n+k-m)$ 。如失敗的話，折線圖必然會與橫線 $y = -1$ 相交，如下圖所示﹕



首先，所有折線圖的數量是 $T = \binom{n+m}{n}$ ，來源可以想像成﹕在 $n + m$ 個時序中任意取 $n$ 個時序進行加一，同樣道理可得出 $\binom{n+m}{m} = \binom{n+m}{n}$ 。如果我們能求所有與 $y = -1$ 相交的折線圖的數量 $S$ ，那麼答案就是 $1 - \frac{S}{T}$ 。說來倒是很容易，但是礙於限制，我們不能直接用公式求算 $S$ 的數量。1978年Cohen利用「反射原理」解決了類同問題，我們也可以試著利用此原理解決問題。

首先留意任何與 $y=-1$ 相交的折線圖，其最後與 $y = -1$ 相交的點，之後必然最終上升至 $(n+m, n+k-m)$ （留意它並非直線上升，中途可能還會下跌，但永遠不會跌至負數值）。這條線從相交點計起長度是 $n+k-m+1$ 。那麼我們試著把這條線「反射」一下，它則一下子掉到 $(n+m, -1-n-k+m-1) = (n+m, m-n-k-2)$ 。例子如下：



藍色點是反射起點，藍色虛線是反射線。留意線過部份反射後的折線圖與原來的圖是一一對應的。另外，新的折線圖擺脫了橫線相交的限制，因為通過反射後折線圖已經肯定是與橫線 $y=-1$ 相交，因此可以看作成在 $(n+m, m-k-n-2)$ 出發，逆時序的加一減一，直至到達 $(0, k)$ 有多少操作，其且每一個圖與原來和橫線相交的圖一一對應。問題是，經這種轉換後我們不清楚被允計使用多少次加一與減一所組成的。設我們被允許 $a$ 次加一 $b$ 次減一，利用反射原理的一一對應關係，我們得到如下式﹕

$$\left\{ \begin{array}{ll} a+b = n+m & \quad \text{(width restriction)}\\ k+a-b = m-n-k-2 & \quad \text{(height restriction)}\\ \end{array} \right.$$

因此我們可得 $a = m - k - 1$ 。而新圖的數量則是 $\binom{n+m}{a} = \binom{n+m}{m-k-1}$ 。又因為每一個新折線圖與原來和橫線相交的圖一一對應，故得 $S = \binom{n+m}{m-k-1}$ 。因此本題的答案是

$$1-\frac{S}{T}=1-\frac{\binom{n+m}{m-k-1}}{\binom{n+m}{n}} = 1-\frac{(m-k)(m-k+1)\cdots m}{(n+1)(n+2)\cdots (n+k+1)}$$


如欲清楚更多反射原理的資料，請參考[1]。

[1] D. I. A. Cohen, Basic Techniques of Combinatorial Theory, John Wiley and Sons, New York (1978).

Topcoder SRM 504 DIV 1 Easy + Medium

題目出得不錯，也挺容易，唯獨最後15分鐘伺服器又出問題，不算rating了。Topcoder應該考慮是否調低參賽者的註冊人數，免得同類事故再發生。

Easy: 大意是有一個 $01$ 字串 $S$ 重覆 $K$ 遍，即 $S' = \underbrace{S\cdots S}_{K\text{ times}}$ 。每一回合把 $S'$ 的首個字元拿出來，如果是 $0$ 的話，則把 $S'$ 餘下的元字順序倒換。如果是 $1$ 的話則把 $S'$ 的字元取逆，即 $S'_i := 1 - S'_i$ 。問通過這個過程裡你能抽到多少個 $1$ 的字元。保証 $S'$ 最多帶 $100000$ 個字元。

做法是保留兩個指針兩個變量。指針一指首一指尾，變量決定元素取前或後和數值需否取逆。然後…就是做。或者可以用STL的deque<T>。

Medium：對於一個 $N \times M$ 的 $01$ -板塊，它依如下程序段修改其內容。

For i = 0 to N-2:
    For j = 0 to M-2:
        //Get the current colors of cells (i,j) and (i,j+1)
        A = Grid(i,j) , B = Grid(i,j+1)

        If (A,B) == (0, 0) Then:
             Do nothing.
        EndIf
        If (A,B) == (1, 0) Then: 
             Mark cells (i+1,j) and (i+1,j+1) as 1.
        EndIf
        If (A,B) == (0, 1) Then:
             Mark cells (i+1,j) and (i+1,j+1) as 0.
        EndIf
        if (A,B) == (1, 1) Then:
             Swap the content in cells (i+1,j) and (i+1,j+1).
        EndIf
    EndFor
EndFor

現在有一輸出 $O$ ，問有多少個輸入可以經以上程序段後得出它。答案取模 $1000000007$ 。

留意幾件事即可。

1. 根據程序段，首行是固定的。
2. 第 $1 \le i < N$ 行的結果 $O_i$ 由 $O_{i-1}$ 來決定的，因為本來的輸入已經被程序段毀掉了。
3. 實際是求對於 $0 \le i \le N-2$ 由 $O_i$ 決定 $O_{i+1}$ 的輸入有多少種。
4. 根據程序段，操作是自左向右處理的。只要把 $O_{i+1}$ 自右至左進行逆操作，理應是要求輸入行有哪些字元可以是任意字元。假設該行有 $K$ 個任意字元，那麼結答案則可以再乘上 $2^K$ 。
5. 哪些逆操作可以決定某元素是否任意字元？留意只有 $(0, 1)$ 和 $(1, 0)$ 才會硬把兩個字元改成一種顏色，其逆操作不能判斷原來的字元。 $(1, 1)$ 的逆操作則與本來操作一樣。 $(0, 0)$ 逆操也作就是甚麼都不幹。
6. 甚麼時候是沒有解？就是進行 $(0, 1)$ 和 $(1, 0)$ 的逆操作時對兩個應修改元素的值與進行其操作後不相符。此時大可以回傳0。

Topcoder Member SRM 503 Easy

沒參加，後來補做Easy。

題意﹕問兩個整數集合 $A, B$ ，能否各自劃分成 $k$ 個離散子集，使得 $A$ 和 $B$ 的第 $i$ 子集必然使得 $A$ 的數全部少於 $B$ 的數。 $k$ 最少是多少？保証 $A, B$ 的數沒重覆。首先想到可以這樣劃分…



但無論你怎樣做，都必然存在最多 $k = 2$ 。如下圖…



甚麼時候是 $k = 1$ ？就是當 $A$ 的最大值少於 $B$ 的最小值。
甚麼時候是 $k = -1$ ？就是當 $A$ 的最大值大於 $B$ 的最大值，或 $A$ 的最小值大於 $B$ 的最小值。

Codeforces #74

上次腦殘之後，人品突然挺好的…

A: 問每個參賽者的答題的分數，成功及失敗的挑戰，問比賽的贏家是誰。保証只有一個贏家。極點頹題。

B: 捉迷藏遊戲。查票員會從火車的頭卡至尾卡不斷的來回檢查，每個時刻只會移動一個車廂。逃票人則在火車移動的時候選擇留守同一車廂，或向附近一車廂移動。如果火車停站了，他可以先行離開車廂，並能進入任意一個車廂，假設這個步驟是不看耗時的。現在給了查票員和逃票人的最初位置，和查票員的行走方向，並保証最後一個時刻是終點站，問給定每個時刻火車是到站還是行走中，逃票人能否不被查票員逮著？即使一定被逮到，最遲必定在甚麼時候被逮著？其實處理上有點麻煩的，對於火車移動的時刻，逃票人的移動有最多3個選擇，並且對查票員的前後移動跟逃票人的距離進行排序，然後往最遠距離的一點移動。如果該距離只能是0的話則會被抓。對於火車停站的時刻，逃票人永遠可以躲在查票員背對的盡頭的車廂，當然，若查票員已站在頭卡或尾卡，則必須站在該對面盡頭即可。寫的時候人品超好，一次就寫對了…

C: 問一個　$N \times M$ 的板，問有多少條不同的桌球的彈道。球的移動遵從45度的斜線運動，碰壁的話會改變方向。卡了很久沒能找到 $O(1)$ 算式…至放棄時想想不如直接寫程序計算一些數值再想想，但之前已經想到一件事﹕彈道必先會經過第一行的其中一個格子。寫的時候想到不用逐步移動，直接可以算出碰在那了。然後在第一行的起點經過剛好3次就能保証遍歷一條完整的彈道。跑的時候跟手算答案一致，無聊試試最大的情況 $N = M = 10^6$ ，竟然不消半晌就跑出答案了﹗後來猛然醒起寫的時候那個直接算出碰撞點可以讓算法變得很高效的…直接提交並通過了。早知一早放棄手寫，然後寫程序找答案還來得有效。後來看tourist的答案… $\text{gcd}(N-1, M-1)+1$ …徹底輸了。

D, E: 待補

Codeforces Round #67

本人極其腦殘的一次比賽，幸好不算rating，否則糟榚。

A: 問兩整數 $A,B$ 把零除去後，其和是否等於 $A+B$ 把零除去的值。頹。

B: 有一社交網站(名字…你懂的)，有三項動作﹕(1)X在Y的留言板上留言 (+15分) (2)X在Y的貼文內留言 (+10分) (3)X讚Y的post。你知道你名字和一系列的動作，每項動作將會替X和Y添加括號內所述的分數。問對於你來說，跟你互動而分數最多至最少的的人的排序是怎樣。即使沒跟你互動都要顯示出來。我錯了幾次是因為沒看到分數是相對於自己…

C: $Q$ 次詢問，每次問區間 $[a, b]$ 內 $\text{gcd}(X, Y)$ 最大的因數。腦殘的爆發點，明明 $O(Q\sqrt{\text{gcd}(X, Y)})$ 可以搞定，我卻寫了質素因數分解，二分找答案…當然是趕急的寫，最後也過不了…

D: 有 $N$ 個小數組，現有 $M$ 個標號，把各標號對應的數組接了起來，問其最大連續子序列和最大是多少。又一腦殘點，漏了個很容易考慮到的情況。首先對每個小數組，求出其左連接最大和，數組和，及右連接最大和。那麼對每標號則考當前和加上數組和是否單調上升。若是則加上數組和並繼續，否則應先更近答案，皆因當前數值可至少加上該標號的左連接最大和使得更大但沒法再向右繼續；之後應從甚麼數開始再繼續？答案就是數組和或右連接最大和之間的最大值。但是注意，每次輸入一個新標號之後，其小數組的最大連續子序列和可能就是唯一答案，必須同時預先比對答案和其數值。我漏了處理這個，連pretest都過不了。

E: 待補。

Codeforces #73 D FreeDiv

題意﹕給了 $N$ 個點，現在接了 $M$ 條藍色邊，一個由藍色邊接成的連通塊稱作藍色領域。現在你可以添加紅色邊使得所有藍色領域都連通起來，但是有限制﹕(1)每點只能接上最多一條紅色邊。(2)每個藍色領域不能接上超過 $k$ 條紅色邊。
根據這個限制，有可能沒法添加紅色邊使得所有藍色領域都連通起來。現問至少需添加多少條藍色邊使得能達成要求？

首先，我們若把所有藍色領域縮成一點，每點標號為 $\min(k, b_i)$ ，當中 $b_i$ 為第 $i$ 個藍色領域的點數。那麼其標號即為限制讓人藍色領域最多可外接多少條紅色邊。現在問題可看成兩種操作﹕
(1) 添加藍邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $\min(b_u+b_v, k)$ 。
(2) 添加紅邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $(b_u+b_v - 2)$ 。

假定不允許操作(1)(即添加藍色邊)，甚麼時候會不能滿足問題條件？明顯是存在兩個點 $u, v$ 使得 $b_u=b_v=1$ 並只能為這兩點進行操作(2)。甚麼時候可以盡量防止這情況發生？留意當 $b_u, b_v \ge 2$ 操作(2)只會製造一個新點 $w$ 使得 $b_w \ge \max(b_u, b_v)$ ，故不會導致失敗。那麼可以先為標號從大到小排序，順著標號進行操作(2)即可，只要當中有標號少於零的即當作失敗。

如果允許操作(1)，怎樣可以把操作(1)的數量最少又使得條件滿足？可用二分搜索答案。假設你只允許進行操作(1) $p$ 次，你會怎樣進行操作(1)使得用上段的方法添加紅邊後條件滿足？不難留意上段說明失敗的情況只有標號為1的點太多的時候才會發生。要避免這個情況，可以考慮每次把兩個標號為1的點用操作(1)連起來，成為一個標號為 $2$ 的點。再由上段可知，它和標號大於2的點添加紅邊，不會出現失敗情況；它杏標號為1的點添加紅邊，會變成只有一個標號為1的點。故把兩兩標號為1的點用藍邊連接最能防止失敗的情況。

我寫的時候用了STL的priority_queue，結果超時(5秒都超…)。改用STL的make_heap之後剛好4.5秒通過了…另，我認為可以不用二分，直接可以算出應最少用多少次操作(1)。

Codeforces #62 D Wormhouse

題意﹕現有一個 $N$ 點的歐拉迴路的遍歷，這遍歷包含 $M$ 條邊。詢問字典序的下一個大的遍歷。可以不存在，圖亦可以不連通。 $3 \le N \le 100, 3 \le M \le 2000$ 。

做法是比較直接的。枚舉迴路的前綴，假設前綴的末點是 $u$ ，本來的下一遍歷點是 $v$ ，則在此刻嘗試找迴路的時候，嘗試的點應至少由 $v+1$ 開始。其餘時候則保持從最小標號點開始。然後直接比較路徑(如有)即可。

Codeforces #12 D Ball

問題非常簡短﹕給了 $N$ 個三維空間的點，問有多少個點 $i$ 使得存在點 $j$ 令 $x_i < x_j, y_i < y_j, z_i < z_j$ 。 $1 \le N \le 500000$ ， $0 \le x_i, y_i, z_i \le 10^9$ 。

其實做法非常經典，屬練習題程度，可是我比較笨，老是想不出正確的方法。

為 $x_i$ 排序，然後把 $y_i$ 離散化。按 $x_i$ 從大至小遍歷，則問題等價於找出 $y_i < y_j$ 並且 $z_i < z_j$ 。再把問題重新看一下則是尋找 $\max_{j: y_i < y_j}\{z_j\}$ 。因 $y_i$ 已離散化則不妨把它看成位置，現求在點 $i$ 的情況下，範圍 $j \in [y_i+1, M]$ 內 $z_j$ 的最大值，當中 $M$ 是指 $y_i$ 有多少個不同的數值(即離散化後的最大值)。如此一來即是求範圍內最大值，線段樹秒殺之。

注意題目要求的是 $x_i < x_j$ 。遍歷 $x_i$ 值從大至小的時候要把相同的 $x_i$ 值暫緩更新，否則會出錯。附一樣例作例子。

3
0 0 0
0 0 1
0 0 1

Codeforces #27 D Ring Road 2

題意﹕給了一個帶 $N$ 個頂點的環 $C_N$ ，現在要添加 $M$ 條邊，你可以把邊畫在環內，或是環外，但必須使得每條邊之間都不能相交(在末端相交除外)。問是否存在一個決定邊的畫法使得條件達成。保証邊連接不同的頂點，沒重邊。

最初有一個很直觀的想法﹕假設邊是 $e = (x, y)$ 且 $x < y$ ，設 $A_e = \{i: x < i < y\}$ ， $B_e = \{1 \cdots N\} - A_e - \{x, y\}$ ，則 $e$ 會把頂點集分開兩半，使得任意邊 $e' = (x', y'), x' \in A_e, y' \in B_e$ 必不能與 $e$ 有相同的畫法。我們稱 $e$ 和 $e'$ 是互斥的。

可惜之後有一個錯的想法。以為順著輸入每條邊，都更新使得互斥的點對的可用的畫法，如遇上某一點對沒有可用的畫法則判無解。這個算法是錯的，只是我未找到反例。

然後有另一個想法，就是基於兩個互斥的點對必須有不同的畫法。可以立刻聯想到的是若把點對看作一個頂點，互斥點對添加一條邊，則此構造圖 $G$ 有解若且僅若 $G$ 是二分的(即可以用兩種顏色為頂點著色)。這就是正確的解。

順帶一提，本題要求的添加邊使得解是一平面圖，但必須基於 $C_N$ 底下該圖仍是平面的。所以不用想平面圖測試的算法了。

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指點。