H - Tomato's Criterion

題目大意

夢月解題目會根據夢月法則？如果題目需要花費大於 $t$ 的時間，則定義題目難度為 hard，反之為 easy。大頭蕃準備 $n$ 個題目請求夢月協助，但隨著每解一題，下一題的難度會隨著疲累值增加，疲累值為一個等差為 $k$ 個數列。只打算解決 easy 的題目，請問在相同的 $t$ 下，不同的 $k$ 分別能解決的最多題數。

題解

如同 Problem B 類似，在固定 $t$ 的情況下，我們希望能夠求出當答案是 $L$ 的時候，允許的最大 $k$ 是多少。我們需要兩件事情：

性質一

固定 $L$ 的時候，隨著 $k$ 越大，最大值會越來越往左邊跑。

證明方向很直觀：因為 $k$ 越大，越左邊的項就會加越多。

性質二

若固定 $L$ 的時候，最大項為 $a[j] + k(L-1-j)$，若這個值超過 $t$，則我們減少 $L$ 的值：$L\leftarrow L-1$。此時，若 $j < L-1$，那麼 $a[j] + k(L-1-j)$ 仍是剩下所有關心的數字之中最大值。

理由也很簡單：大家一起減 $k$，所以原本的最大值還是最大值。

就是那個單調性啊...

所以，事情變得很簡單啦，先假定輸入的序列已經由小到大排好序了。對於一個固定的 $L$，我們可以記錄每個數字「超過」下一個數字的那個 $k$ 值是什麼：也就是說，我們想要知道的是

$a[i] + k (L-1-i) \ge a[i+1] + k(L-1-i-1)$

在什麼 $k$ 的時候會發生。可是這等價於：

$a[i] + k \ge a[i+1]$

因此！我們可以輕鬆知道每一個 $a[i]$ 相較於下一個數字，當 $k\ge a[i+1]-a[i]$ 的時候，它會取得領先的地位。現在我們可以連續看三個數字：若第一個數字 $a[i]$ 超越第二個數字 $a[i+1]$ 的那個 $k$ 值，比第二個數字超越第三個數字 $a[i+2]$ 的那個 $k$ 值，來得小。表示當 $a[i+1]$ 超越 $a[i+2]$ 的時候， $a[i]$ 保證也超越了 $a[i+2]$，此時無論如何 $a[i+1]$ 都不會是最大值了！

於是這引導我們得到一個 stack 的 solution，對於一個 $L$，我們維護一個堆疊，從左到右是那些隨著 $k$ 變大，真的有機會變成最大值的那些 index：$i_1, i_2, \cdots, i_s$，對於相鄰的兩個 $i_r, i_{r+1}$，我們可以輕易計算出，當 $k \ge \frac{a[i_{r+1}] - a[i_r]}{i_{r+1} - i_r}$ 的時候，第 $i_r$ 項會取代 $i_{r+1}$ 成為新的最大值。

除了堆疊以外，我們還需要有一個「箭頭」指向對於現在這個 $L$，最大的 $k$ 是什麼、最大值出現在哪裡。由於性質一、二，當 $L$ 變大的時候，$k$ 會變小，而且最大值會往後推；因此這個「箭頭」只會隨著 $L$ 變大而往後推進。

最後，是什麼樣的條件會讓這個「箭頭」往後推呢？假定 $a[i_r]$ 是當前的最大值，我們可以輕易算出滿足題目要求的最大 $k = \frac{t - a[i_r]}{ L-1-i_r }$ 如果它比 $\frac{a[i_{r+1}] - a[i_r]}{i_{r+1} - i_r}$ 來得大，表示目前這個 $k$ 很安穩（的確是當前最大值）；若該值相較之下比較小，表示在這個 $k$ 的時候，最大值另有其人，此時令 $r\leftarrow r+1$，繼續檢查下一個 $a[i_r]$。

當然，隨著 $L$ 增加，若最後一個 $i_s$ 被 pop 掉了，也要記得把這個「箭頭」拉回來。整個演算法的時間複雜度便是排序 + 堆疊 + 詢問二分搜的時間：$O(n\lg n + n + Q\lg n)$。很棒的小品演算法對吧 :)