slope trick 用于優化一類二維 dp 問題。對于 \(f_{i,j}\)，我們希望對于所有 \(i\)，\(f_i\) 是連續的分段函數，并且具有凸性。特別地，我們希望每一段的斜率（即差分）都是整數，當然對于貢獻是整數的題目來說這通常還是比較顯然的。

顯然有一些固有的函數滿足上述性質，例如絕對值函數、一次函數等。

思想上，我們嘗試把 \(f_i\) 寫成凸包的形式。我們考慮維護一個可重集表示所有斜率發生變化的位置，其中為了表示變化量，我們將變化的位置寫 \(\Delta k\) 次就可以意味著斜率的變化量為 \(\Delta k\)。

當然這并不能唯一確定凸包。所以我們還需要維護一根線的表達式，不妨取最左側那一根，維護它的斜率與截距 \(k_0,b_0\)，我們可以認為將可重集中的所有位置從小到大寫出來之后，\(i\) 上的斜率是 \(k_0+i\)（對于下凸）。

考慮我們得到了這個可重集之后可以簡單地完成很多麻煩的轉移操作：

• 合并兩個滿足性質的函數：直接合并可重集，然后 \(k_0,b_0\) 也對應相加。
• 取前后綴 \(\min\)：去掉 \(k<0\) 或者 \(k>0\) 的部分，維護 \(k_0,b_0\)。
• 求 \(\min\)：提取 \(k=0\) 的部分。
• 平移/翻轉：修改可重集打全局標記，維護 \(k_0,b_0\)。

具體還需要根據實際情況選擇數據結構和數據結構意義刻畫。通常我們使用堆和平衡樹等能夠維護大小關系的數據結構來維護這個可重集。

P4597 序列 sequence

考慮顯然的 dp，有：

歸納容易證明 \(f_i\) 是下凸的。

考慮轉移是我們要塞一個絕對值函數進去，然后刪掉所有 \(k<0\) 的部分。

注意到我們可以暴力維護可重集，原因是每次插入只會導致斷點 \(a_i\) 處一個點上的斜率增加 \(2\)。所以我們直接維護一個大根堆表示可重集中從左到右的情況，同時維護 \(k_0,b_0\) 即可。

注意到每次操作都必然會導致 \(k_0\) 減小 \(1\)。但由于前綴 \(\min\) 的存在，我們恰好會彈掉一個斷點來使得 \(k_0\) 變回 \(0\)。這些優美的性質使得我們每次操作時只需彈出一次最左側的斜率恰為 \(-1\) 的線段，并且答案就是 \(b_0\)。