<style> .reveal .slides { text-align: left; font-size:30px } </style> # DP 優化 & 一些幾何 ---- - Convex Hull Optimization - Divide and Conquer Optimization - Li Chao Segment Tree - Dynamic Convex Hull --- ## Convex Hull Optimization ### DP 斜率優化 ---- 先來複習單調隊列優化 轉移式大概長這樣 `dp[i] = a[i] + min/max{dp[j]} (i-k `$\le$` j < i)` 並且運用其單調性將複雜度從 `O(nk)` 降到 `O(n)` ---- ## 轉移式 而斜率優化的轉移式通常會長這樣 <div style="font-size:32px"> `dp[i] = a[i] + min/max`$_{j<i}$`{dp[j]+` <span style="color:red"> `x[i]*m[j]`</span>`+b[j]`} </div> 會發現紅色部分，跟 `i、j` 都有關 這時候就不能用單調隊列優化 ---- ## 幾何意義上的性質 以下面這條轉移式為例 `dp[i] = a[i] + max`$_{j<i}$`{dp[j]+x[i]*m[j]+b[j]}` 對於每個 `j` 可以視為一條斜率為 `m[j]` 、截距為 `b[j]` 的直線 計算 `dp[i]` 可以視為把 `x[i]` 帶進去所有的直線 `y = m[j] * x[i] + b[j]` 中取最大的那條 + `a[i]` ---- ## 幾何意義上的性質 `y = m[j] * x[i] + b[j]` 中取最大的那條加上 `a[i]`  ---- 每次對於 `x[i]` 要找出所有直線中帶進去最大的 y 等價於對於這些直線，維護下凸包  ---- ## 性質 對於這些下凸包上的直線 假設有兩條分別為 $L_1:m_1x+b_1$ 和 $L_2:m_2x+b_2$ 且 $m_1 < m_2$，必定有個分界點(交點) $x*$ 使得 $x*$ 以左帶進去 $L_1$ 比較大 $x*$ 以右帶進去 $L_2$ 比較大  因此下凸包從左到右的直線斜率會遞增 ---- ## 如何維護下凸包 ---- ### case 1. 斜率 m[i] 遞增、詢問 x[i] 遞增 * 斜率 m[i] 遞增 插入的直線遞增代表每次插入一定會放到下凸包的最右邊 因此每次插入新直線時，先判斷當前在下凸包上最後一條直線會不會被覆蓋，會要先刪除 * 詢問 x[i] 遞增 詢問的位置遞增則可以跟單調對列優化的做法相同，只需維護到當前的詢問位置 x[i] 為止， 的下凸包最左邊會詢問到哪，更左的直線都可以刪除 作法如同單調對列優化：可以用 deque 維護 `push_back`, `pop_front`, `pop_back` 等操作 ---- ### case 2. 斜率 m[i] 遞增、詢問 x[i] 不單調 * 斜率 m[i] 遞增 如同前一種 case，好好維護下凸包最右端的直線，把不會出現在下凸包上的直線刪除 * 詢問 x[i] 不單調 如果不單調，代表用到的直線不一定在最左端，則我們可以透過二分搜找詢問位置 x[i] 的是哪一條直線維護的 只需要 `push_back`, `pop_back` 可以用 vector 維護 ---- ### case 3. 斜率 m[i] 不單調、詢問 x[i] 遞增 * 斜率 m[i] 不單調 下凸包可以改用 set 維護，判斷 m[i] 要插入的位置會不會讓下凸包更好，會就插入並且往左右判斷會不會使得相鄰的直線不在下凸包上，會就從 set 上刪掉 * 詢問 x[i] 單調 如同單調對列，當 set 最前面的線段過期了就丟掉 ---- ### case 4. 斜率 m[i] 不單調、詢問 x[i] 不單調 由於兩者都沒單調性，若用 set 維護 詢問會變不好做 除非自己刻一棵 Treap 維護 或者可以用 [下凸包模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/lowerConcaveHull3.cpp) 或者 [李超線段樹](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/geometry/LiChaoST.cpp) 維護 ---- ## 操作 - insert line(ax+b) 插入一條一次方程式 - query f(x) 詢問 $x=Si$ 時最大的 $y$ 是多少 兩個操作都是 $O(\log N)$ ---- ## 引入例題 [HNOI 2008 玩具裝箱](https://vjudge.net/problem/LibreOJ-10188) 有 $n$ 個玩具，第 $i$ 個玩具價值為$C_i$。要求將這 $n$ 個玩具排成一排，分成若干段。對於一段$[l, r]$，它的代價為$(r-l+ \sum_{i=l}^{r}C_i -L)^2$。求分段的最小代價。 <span>先來列出轉移式吧!<!-- .element: class="fragment" data-fragment-index="1" --></span> ---- 再來看看範圍 $1\le n\le 5\times 10^4$ 太大不能 $O(N^2)$ QQ ---- 接著就是斜率優化出場的時候 ---- ## 作法 1. 列出轉移式 2. 簡化轉移式變成一次函數 `ax+b` 3. 維護下凸包 4. AC ---- ## 轉移式 $[l, r]$ 公式：$(r-l+\sum_{i=l}^{r}C_i -L)^2$ `dp[i] = min`$_{j<i}$`{ dp[j] + (pre`$_{i}$`-pre`$_{j}$`+i-(j+1)-L)`$^2$` }` 其中 `pre`$_{j}$ 為 $\sum_{i=1}^{j} C_i$ ---- `dp[i] = min`$_{j<i}$`{ dp[j] + (pre`$_{i}$`-pre`$_{j}$`+i-(j+1)-L)`$^2$` }` 整理一下公式 令 `S`$_{i}$ = `pre`$_{i}$` + i` `L' = L+1` $\to$ `dp[i] = min`$_{j<i}$`{ dp[j] + (S`$_{i}$`-S`$_{j}$`-L')`$^2$` }` ---- 再把跟 `j` 無關的變數移到左邊 `dp[i] = min`$_{j<i}$`{ dp[j] + (S`$_{i}$`-S`$_{j}$`-L')`$^2$` }` 先包起來 `dp[i] = min`$_{j<i}$`{ dp[j] + ((S`$_{i}$`-L')-S`$_{j}$`)`$^2$` }` $\to$ `dp[i]-(S`$_{i}$`-L')`$^2$ `= min`$_{j<i}$`{ dp[j] + S`$_{j}$$^2$` - 2 S`$_j$`(S`$_i$`-L')}` ---- 整理等式右邊 `dp[i]-(S`$_{i}$`-L')`$^2$`= min`$_{j<i}$`{dp[j]+S`$_{j}$$^2$`-2S`$_j$`(S`$_i$`-L')}` $\to$ `dp[i]-(S`$_{i}$`-L')`$^2$`= min`$_{j<i}$`{dp[j]+S`$_{j}$$^2$`+2S`$_j$`L'-2S`$_i$`S`$_j$`)}` ---- `dp[i]-(S`$_{i}$`-L')`$^2$`= min`$_{j<i}$`{dp[j]+S`$_{j}$$^2$`+2S`$_j$`L'-2S`$_i$`S`$_j$`}` 把右側只跟`j`有關的變數設成`b` `b = dp[j] + S`$_{j}$$^2$`+2S`$_{j}$`L'` 跟`i、j`都有關的設成 `ax` `ax = -2S`$_i$`S`$_j$ 變成 `dp[i]-(S`$_{i}$`-L')`$^2$`= min`$_{j<i}$`{ax+b}` ---- ## 一次函數 ax + b `ax = -2S`$_i$`S`$_j$ `b = dp[j] + S`$_{j}$$^2$`+2S`$_{j}$`L'` 其中 `a`為`-2S`$_{j}$ `x` 為當前的 `S`$_{i}$ ---- ## 求 dp[i] 下凸包求當前位置 y 的最大值，但題目是求最小值，因此要加負號 `dp[i]-(S`$_{i}$`-L')`$^2$`= min`$_{j<i}$`{dp[j]+S`$_{j}$$^2$`-2S`$_j$`L'+2S`$_i$`S`$_j$`}` ```cpp= dp[i] = -eval(S[i]) + (S[i]-L')*(S[i]-L'); ``` ---- ## 插入一次方程式 下凸包求最大值，但題目是求最小值，因此要加負號 `a = -2S`$_j$ `b = dp[j] + S`$_{j}$$^2$`+2S`$_{j}$`L'` ```cpp= insert_line(2*S[j], -(dp[j]+S[j]*S[j] + 2*S[j]*L')); ``` ---- ## 複雜度 `dp[i] = min`$_{j<i}$`{ dp[j] + (pre`$_{i}$`-pre`$_{j}$`+i-j-1-L)`$^2$` }` 原本的 $O(N^2)$ 降低到 $O(N\log N)$ ---- ## 單調隊列優化 一樣用 deque 維護 deque 維護在下凸包上的直線  ---- 可以發現每次丟進去 ax+b 的 x (詢問) 都是遞增的 x 為 S$_i$ = `pre`$_{i}$` + i`  因此放在左邊的線會過期 ---- ## 檢查過期  直接用當前的詢問 x 帶進去，如果 deque 裡最左的兩條直線相比 $a_{1}x+b_1\le a_{2}x+b_2$ 則代表最前面的線過期了 就可以直接 pop 掉 ---- ## 新增當前的線 而這題新增的線段也是斜率遞增的 因此也有單調性 ---- ## 新增當前的線 假設紅色為當前要新增的線，藍色為原本的最後一條線  會發現如果新增紅色線的話，藍色線就沒用了(不在下凸包上) 因此每次新增線的時候要檢查是否在會讓前一條在移除凸包 ---- ## 檢查是否移除 下圖可以看到下凸包裡最後一條線與倒數第二條線的交界在 x=h 的位置，而我們可以檢查最後一條線$a_1$x+$b_1$ 跟 欲新增的線 $a_2$x+$b_2$的大小關係，如果 $a_1$x+$b_1$ < $a_2$x+$b_2$ 則可以刪除最後一條線 刪除後再把新的線加進去  ---- 下凸包求最大值，但題目是求最小值，因此要加負號 ```cpp= deque<pair<ll,ll>> deq; //ax+b int eval(ll x){ return deq.front().first*x+deq.front().second; } void solve(){ for(int i=0;i<n;i++){ while(前面過期) deq.pop_front(); dp[i] = -eval(s[i]) + (S[i]-L')*(S[i]-L'); while(最後一條被覆蓋) deq.pop_back(); deq.push_back({2*S[i], -(dp[i]+S[i]*S[i] + 2*S[i]*L')}); } } ``` ---- ## 漂亮的寫法 線段也可以用結構包起來，多載 () ```cpp struct line{ int a, b; int operator() (int x){ return a * x + b; } }; ``` 詢問時就能直接 l(x) 求出當前直線在 x 的值 ```cpp line l; cout << l(x) << endl; ``` reference: [DP斜率優化I](https://hackmd.io/@yuspring/SylgZEOpu) ---- 如此以來就能在 $O(n)$ 做完了! --- ## Divide and Conquer DP ### 分治優化 ---- - 常見 2D/1D 轉移式：$dp(i, j)=\min\limits_{1\le k\le j}\{dp(i-1, j) + f(i,j)\}$ - 且第二維度 $j$ 滿足凸性 - 滿足凸性也就是令 $p[i][j]$ 代表 $dp[i][j]$ 的轉移點為 $k$，那麼滿足凸性代表會有 $p[i][1]\le\dots\le p[i][m],\forall i$ - $dp(i-1, j) + f(i,j)$ 代表 $dp(i, j)$ 的計算只跟 $dp[i-1][k]$ 和其他資料有關，不需要用到任何 $dp[i]$ ---- 上述會有兩個性質 - 一個是 $dp[i][1\sim j]$ 的計算順序不重要可以任意選擇計算順序（因為只依賴 $dp[i-1]$ 層的東西，以及該方向上有轉移點單調遞增的性質 - 既然有轉移點單調遞增，那麼假設算好了 $dp[i][j]$ 和 $dp[i][k]$ 的值且 $j<k$，那麼對於所有 $j<r<k$ 都可以知道轉移點會滿足 $p[i][j]\le p[i][r]\le p[i][k]$，那麼在計算 $dp[i][r]$ 的最大值時只需要考慮枚舉 $p[i][j]\sim p[i][k]$ 這個範圍內即可 ---- - 因此就可以考慮套用分治： - 假設現在要計算 $dp[i][l\sim r]$ 且轉移點範圍已知是 $vl\sim vr$ - 那麼先暴力（直接枚舉掃過所有 $vl\sim vr$ 找出最大值）計算出 $dp[i][m=\frac{l+r}{2}]$ 位置的值及其轉移點 $vm=p[i][m]$，那麼之後就能知道 $l\sim m-1$ 的區間只需要考慮 $vl\sim vm$，而 $m+1\sim r$ 的範圍則是只要考慮 $vm\sim vr$ - 直接遞迴下去分別做這兩部份即可 - 初始化則是 $l=1,r=m,vl=1,vr=m$ 之類的 ---- ### 複雜度 - 可以看出這個作法非常簡單非常暴力，只有一個短短且實做很直觀簡單的遞迴分治而已，對於計算函數 $f$ 除了要通靈/證明出他具有凸性且不依賴 $dp[i]$ 之外，不需要額外的性質 - 複雜度則是能從暴力計算的 $O(nm^2)$ 降至 $O(nm\log m)$ 以 n, m = 3000 為例 $O(nm\log m)\to 10^8\to AC$ ---- ### Houses and Schools 有 $n$ 個房子在一維數線上，兩個房子在位置 a, b，則距離為 |a-b| 而要選 $k$ 個點建立學校，使得每個房子到最近的學校距離總和最小。 - subtask 1 : n, k = 300 [link](https://zerojudge.tw/ShowProblem?problemid=e165) - subtask 2 : n, k = 3000 ---- ## 轉移式 `dp[k][n]` 建了 $k$ 個學校覆蓋前 $n$ 個房子的最小距離總和 轉移為每次從 dp[k-1][$j$] 轉移，代表前 k-1 個學校覆蓋前 $j$ 個房子 而第 $i$ 個學校覆蓋 $(j+1)\sim n$ 個房子 (設置點為第 $(j+1)\sim n$ 個房子的中點) $dp[k][n] = _{j<n}min(dp[k-1][j] + sum(j+1, n))$ 直接做複雜度 $O(kn^2)$ ---- $dp[k][n] = _{j<n}min(dp[k-1][j] + sum(j+1, n))$ 觀察以上 dp 式可以發現 dp[k][n] 只跟 dp[k-1] 有關， 且轉移點有凸性(每次選的房子只會往右) 因此可以使用 分治優化 ---- ## 核心程式碼 ```cpp= void solve(int k, int l=1, int r=n, int vl=1, int vr=n){ if(l > r) return; int mid = (l + r) >> 1, p = 0; dp[k][mid] = 1e18; for(int i = vl; i <= min(vr, mid - 1); i ++){ if(dp[k][mid] >= dp[k - 1][i] + f(i,j)){ //窮舉最佳轉移點 dp[k][mid] = dp[k - 1][i] + f(i,j); p = i; } } solve(k, l, mid - 1, vl, p); // dp[i][1~mid-1] 的轉移點會在區間 vl~p 之間 solve(k, mid + 1, r, p, vr); // dp[i][mid+1~r] 的轉移點會在區間 p~vr 之間 } solve(k, k, n, 1, n); ``` --- ## 李超線段樹 能處理的問題: - 在二維平面中插入一個一次函數 $f(x) = ax+b$ - 給定 $x$，查詢最大/最小 $f(x)$ ---- 每個節點儲存一個區間的線段 ``` struct{ node *l, *r; line f; } ``` 並且線段樹一樣，有左右子節點，直到區間 l = r 為止 以及儲存一個線段 f，為這段區間完整覆蓋的線段 接下來的例子以查詢最大值為例 ---- ## 插入線段 以動態開點線段樹實做，如果當前區間沒有線段，則把線段 $v$ 設成當前區間的線段。 ```cpp void insert(line v, int l, int r, node *nd){ if(nd == nullptr){ nd = new node(v); return; } } ``` 而如果該線段本來就有區間呢? ---- 可以分為以下兩種 case ### case1: 新的函數完全覆蓋/被覆蓋  如果完全覆蓋則把當前區間的函數換成新的。 ---- ### case2: 兩條線在區間內有交點 以區間中間切一半，必定有其中一個子區間(左半或右半)， 被其中一個函數完全覆蓋。 以下圖為例，藍色函數覆蓋了整個右半區間，而左半的答案不確定，因此使用藍色函數當成當前區間的函數，而左半區間繼續遞迴，直到區間完全被同一個函數覆蓋或者區間 Left = Right 為止。  而其實不需要考慮 Left = Right 的 case，因為此 case 能被恰好一個函數所覆蓋。 ---- ## 給定 $x$，查詢最大 $f(x)$ 直接來看 code，查詢時如果到位置 x，則回傳當前區間的函數 $f(x)$ 值，否則回傳值為 max {當前區間的函數值,根據 x 往左/右區間的最大函數值} ```cpp= LL query(int x, int l, int r, node *nd){ if(!nd) return -INF; if(l == r) return nd->f.eval(x); if(mid >= x) return max(nd->f.eval(x), query(x, l, mid, nd->l)); return max(nd->f.eval(x), query(x, mid + 1, r, nd->r)); } ``` ---- 回顧插入函數時，在區間內有交點的情況  如果 x 在右半區間，則答案在當前區間就能求出來， 因此所有走過的區間的函數都要 query 若 x 在左半區間，則插入線段會繼續遞迴處理 根據以上就能好好維護所有區間的最大函數值了 ---- ## 插入的函數改為區間 在二維平面中插入一個一次函數 $f(x) = ax+b$ 在區間 $[l, r]$ 把函數拆分到線段樹上的 $\log n$ 個區間， 對每個區間進行 insert ```cpp= void update(line v, int ql, int qr, int l, int r, node *nd){ if(nd == nullptr) nd = new node(); if(ql <= l && r <= qr){ insert(v, l, r, nd); return; } int mid = (l+r)/2; if(ql <= mid) update(v, ql, qr, l, mid, nd->left); if(qr > mid) update(v, ql, qr, mid+1, r, nd->right); } ``` ---- ## 複雜度 插入一個函數複雜度為 $O(\log n)$， 而如果插入的函數為區間插入則要拆成 $O(\log n)$ 個分別插入 複雜度為 $O(\log^2 n)$ 詢問為 $O(\log n)$，每次遞迴到最深 --- ## Dynamic Convex Hull ### 動態凸包 有 $q$ 筆操作，每次操作為以下其中一種: - 平面上加入一個點 $(x, y)$ - 每次詢問一個點 $(x, y)$ 是否在凸包內 ---- 只有詢問可以直接砸模板， 而新增點呢? ---- 回到找凸包的算法 Andrew’s Monotone Chain 分成上下凸包，分別維護 ---- 加入一個新的點時，如果可能構成更大的凸包， 如何快速的找到在原本上/下凸包上要改變的位置? <span><!-- .element: class="fragment" data-fragment-index="1" -->使用 set !</span> ---- 由於上/下凸包上的點分別都有照 x, y 排序，因此有單調性，可以在上面二分搜。 對於新增的點位置，在 set 上二分搜 ---- 對於新增的點，如果本來就在凸包內/上，則不用任何操作 否則要判斷當前新增的點，凸包上位置的左右兩側的點是否需要刪除(判斷外積) 記得好好處理上下凸包 $\le 3$ 個點的情況  以上圖為例，新增綠色點時，右側的點需要被移除。 ---- ## 複雜度 每次判斷/新增點，複雜度 $O(\log n)$ 每個點最多被移除一次，均攤下來複雜度是好的 $q$ 筆操作，總複雜度 $O(q\log n)$