模拟賽 序列

題意：

（\(n,m\le10^6\)）

​ 題目所給表達式涉及區間和。将原式轉化為字首和形式：

\[f(l,r)=suma_r-k\times sumb_r-(suma_{l-1}-k\times sumb_{l-1})

\]

​ 我們設 \(V_i=suma_i-k\times sumb_i\)。那麼\(f(l,r)=V_r-V_{l-1}\)。那麼我們在 \([p,n]\) 取 \(V_{max}\)，在 \([0,p-1]\) 取 \(V_{min}\) 就能得到答案。

​ 注意到 \(V_i\) 的形式與一次函數的形式相同，容易想到斜率優化。我們考慮維護 \([1,p]\) 區間的下凸殼和 \([p,n]\) 區間的上凸殼。由于維護凸殼我們需要保證一段區間的斜率單調。如果直接對每一段區間先排序再 \(O(n)\) 單調棧維護，時間複雜度是 \(O(n^2\log n)\) 的。是以我們可以考慮線段樹。由于題目中沒有修改操作，是以重點就是在于如何合并兩端區間。

​ 由于我們要保證單調性，又因為線段樹是遞歸建樹的，我們很容易想到歸并排序的方式來保證單調性。然後用一個單調棧掃一下維護上下凸殼。

​ 查詢的時候，我們可以二分決策點，找到凸殼中最佳決策點然後選擇。

​ 那麼空間複雜度是 \(O(n \log n)\) ，而時間複雜度是 \(O(n\log n\log n)\)。這已經可以通過本題了（有資料水的原因）。

​ 這裡可以繼續優化，考慮優化掉查詢時的二分。由于這題不是強制線上，我們可以将詢問按 \(k\) 的大小排序，然後查詢時用單調隊列代替掉二分。那麼時間複雜度就做到了 \(O(n\log n)\)。（但是我太懶了沒寫）

​ 這裡值得注意的一點線段樹每個節點的棧如果直接存 \(V_i\) 的資訊會 MLE。由于 \(V_i\) 一共隻有 \(n\) 個，是以我們線上段樹每個節點的棧裡存編号就好了。

​ （關鍵的一點是不要把棧的彈出那行的 while 寫成 if，不然就會調一個晚上）

代碼如下：（沒有離線詢問，複雜度還是 \(O(n\log \log n)\)）

路漫漫其修遠兮，吾将上下而求索。