算法隨筆合集

2025.6.27 ST 表

可以做到 $O(n\log n)$ 預處理， $O(1)$ 回答詢問.

原理是預處理 $f_{i,j}$ 維護每個左端點 $i$ 開始長度為 $2^j$ 的區間信息，把每個詢問區間拆成可能重疊的兩個區間來回答. 所以 ST 表使用的前提是查詢重復信息不會改變結果，比如最值、$gcd$ 之類的，比較神秘的有區間按位或和區間按位與.

有幾處邊界細節需要注意：

預處理層數上界 $\lfloor\log_2n\rfloor+1$.
預處理保證右端點不超過 $n$，即 i + (1 << j) - 1 <= n.
對于詢問 $l,r$，層數 $s=\lfloor\log_2(r-l+1)\rfloor$，則兩區間對應 $f_{l,s}$ 與 $f_{r-(1 << s) + 1,s}$.

求對數不必預處理，可以用內置函數 __lg().

2025.7.7 歐拉路徑，歐拉回路

一個圖存在歐拉回路當且僅當：

非零度點互相（強）連通.
點的度數都是偶數（或出度入度）.

一個圖存在歐拉路徑當且僅當：

非零度點互相（強）連通.
恰好有 $2$ 個奇度點（或恰好存在兩點 $u,v$ 滿足一個出度比入度多 $1$，一個入度比出度多 $1$）.

2025.7.10 背包

01背包
可滾動數組，必須倒敘枚舉容量 $j$ 否則可能選到多個相同物品. 時間復雜度 $O(nW)$.

\[f_{i,j}=\max(f_{i-1,j}, f_{i-1, j-w_i}+v_i) \]

完全背包
可滾動數組，必須正序枚舉容量 $j$ 因為可以選多個物品. 時間復雜度 $O(nW)$.

\[f_{i,j}=\max(f_{i,j}, f_{i, j-w_i}+v_i) \]

多重背包
直接 DP 時間復雜度是 $O(W\sum k_i)$. 利用二進制分組可以做到 $O(W\log \sum k_i)$；利用單調隊列優化可以做到 $O(nW)$.

\[f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+k\times v_i) \]

混合背包
物品之間互不干擾，直接分別 DP 即可.

分組背包
遍歷每個組跑 $01$ 背包即可.

2025.7.11 wqs 二分

ref：https://www.luogu.com.cn/article/hbx1okqa

wqs 二分，也叫凸單調性優化，是一類與函數凹凸性有關的 DP 優化.

假如我們有一個 $f(x)$，已知其具有凸性（即導函數單調，數學上一般叫凹函數或凸函數），但是它的最值因為某些限制很難求. 此時我們可以引入一個參數更多的函數 $G(x,k)=f(x)-kx$，如果這個函數在 $k$ 確定時關于 $x$ 的極值好算，那么我們就可以間接求出 $k$ 不同時 $f(x)$ 的取值. 這時候我們其實并沒有考慮 $ x $ 的限制，但是根據凸性，$x$ 此時也具有單調性，則現在有 $ f(x)=kx+G(x,k) $ 是關于 $k$ 的單調函數，二分 $k$ 即可求得 $f(x)$ 最值.

為什么 $G(x,k)$ 相比于 $f(x)$ 會好求？在 OI 中，我們可以理解為加入的 $k$ 使得我們暫時忽略了某個 $x$ 的限制，但是 $x$ 卻有關于 $k$ 單調的性質，而且我們算 $G(x,k)$ 時能很容易地把此時的 $x$ 求出來，那么我們就直接把 $k$ 當未知數進行二分，根據 $x$ 判斷即可. 實際上不必過分關注凸性.

另外 $G(x,k)$ 的極值點可能不唯一確定，也就是函數圖像的極值呈平行于 $ x $ 軸的一條線段，這時候顯然應該取兩端點中的一個更優. 一般來說求最小值取左端點，求最大值取右端點，但是具體情況還需要具體分析.

綜上，當你確定 $ f(x) $ 的凸性，或者直接確定 $ x $ 關于另一個 $ k $ 單調且 $G(x,k)$ 好求等等性質時可以使用 wqs 二分進行優化.

wqs 二分涉及的思想是主元法，限制很強. 事實上它理應具有很強的可拓展性，即不同的 $G(x,k)=f(x)+A(x)$ 可能適用于更多的情況.

2025.7.14 決策單調性與（二分）單調隊列

決策單調性

決策單調性即決策點具有單調性，通常是下標單調遞增.
更一般的，一個二元函數 $w(x,i)$ 在 $w(p_i,i)$ 時最優則 $p_i$ 為決策點，那么對于 $j<i$，決策單調性可以定義為：

\[\forall j<i,p_j\le p_i \]

要證明某函數 $w(x,y)$ 滿足決策單調性，即證明：

\[f_{p_i} +w(p_i,i) 優于 f_{p_j}+ w(p_j,i),并且f_{p_j}+w(p_j,j)優于f_{p_i}+w(p_i,j) \]

一旦 $w(x,y)$ 滿足決策單調性，我們就可以使用單調隊列來維護決策點.

二分隊列

二分隊列要根據決策單調性來維護隊頭 $h$ 和隊尾 $t$，隊列里面存三元組 $(l_j,r_j,p_j)$ 表示 $[l_j,r_j]$ 的最優決策是 $p_j$. 容易發現隊列中的所有 $(l_j,r_j)$ 將 $[1,n]$ 劃分開. 現在我們要找到 $i$ 的最優決策點，并且根據 $i$ 去更新后面的最優決策點.

$i$ 的最優決策點在之前已經更新過了，所以我們從隊頭開始，把所有 $r_h < i$ 的三元組彈出，因為其不以 $i$ 作為最優決策，根據決策單調性也不會作為 $[i+1,n]$ 的最優決策. 直到 $i$ 在 $[l_h,r_h]$ 之間，那么我們直接取出 $p_h$ 來求 $i$ 的答案.

現在我們考慮怎么找到后面的一個區間以 $i$ 為最優決策. 根據決策單調性，其一定對應最末的區間，也就是找隊尾 $(l_{t_0},n,i)$ 中的 $l_{t_0}$，這意味著我們可能要先舍去隊尾的一些三元組. 我們找出 $p_t$ 和 $i$ 決策的轉折點 $x$，滿足 $x'<x$ 時 $w(p_{t},x')$ 優于 $w(i,x')$，$x'>x$ 時 $w(i,x')$ 優于 $w(p_{t},x')$. 當 $l_t\ge x$ 時，$i$ 會作為 $[l_t,r_t]$ 完整區間的決策點，但是轉折點 $l_{t_0}$ 并不在區間中，所以彈出隊尾. 直到第一次出現 $x>l_t$，$x$ 就是我們要找的 $l_{t_0}$，此時將其加入隊尾.

實現時實際上不用存三元組中的 $r$，只需要存一下決策轉折點 $l$ 就足夠了.

二分隊列與單調隊列的區別體現在二分隊列是維護的函數交點的單調，而單調隊列直接維護的下標單調，少套了一層映射關系. 所以實際應用時要根據題目具體分析.

2025.7.16 FFT

FFT 優化 DFT

考慮將多項式

\[A(x)=a_0+a_1x^1+a_2x^2\cdots+a_{n-1}x^{n-1} \]

按下標奇偶拆成兩個次數減半的多項式 $A^{[0]}(x),A^{[1]}(x)$：

\[A^{[0]}(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{{n\over2}-1}\\ A^{[1]}(x)=a_1+a_3x+a_5x^2+\cdots+a_{n-1}x^{{n\over2}-1}\\ \]

就可以得到下式：

\[A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2) \]

那我們求 $A(x)$ 的 $n$ 個點值，就轉換成分別求 $A^{[0]}(x^2),A^{[1]}(x^2)$ 的 ${n\over 2}$ 個點值，再根據上式進行合并即可.

這樣直接求仍然是 $O(n)$ 的，但是這個 $x\rightarrow x^2$ 的轉化啟發我們用折半引理的結論對數據規模進行簡化.

于是考慮求

\[\omega_n^0,\omega_n^1,\omega_n^2,\cdots,\omega_n^{n-1} \]

處的點值，每次平方數據規模都可以減半，就可以做到只求 $O(\log n)$ 次而不是 $O(n)$ 次. 具體的：

\[A(\omega_n^i)=A^{[0]}(\omega_n^{2i})+\omega_n^iA^{[1]}(\omega_n^{2i})\\ A(\omega_n^{i+{n\over2}})=A^{[0]}(\omega_n^{2i+n})+\omega_n^{i+{n\over 2}}A^{[1]}(\omega_n^{2i+n}) \]

其中下式可以進行化簡：

\[\begin{aligned} A(\omega_n^{i+{n\over2}})&=A^{[0]}(\omega_n^{2i+n})+\omega_n^{i+{n\over 2}}A^{[1]}(\omega_n^{2i+n})\\ &=A^{[0]}(\omega_n^{2i}\cdot w_n^n)+\omega_n^{i}\cdot w_n^{n\over2}A^{[1]}(\omega_n^{2i}\cdot w_n^n)\\ &=A^{[0]}(\omega_n^{2i})-\omega_n^iA^{[1]}(\omega_n^{2i}) \end{aligned} \]

即有：

\[\begin{aligned} A(\omega_n^i)=A^{[0]}(\omega_n^{2i})+\omega_n^iA^{[1]}(\omega_n^{2i})\\ A(\omega_n^{i+{n\over2}})=A^{[0]}(\omega_n^{2i})-\omega_n^iA^{[1]}(\omega_n^{2i}) \end{aligned} \]

所以每次數據計算數據規模都可以翻倍，只用求 $O(\log n)$ 次點值，DFT 的時間復雜度就來到了 $O(n\log n)$.

FFT 優化 IDFT

IDFT 是 DFT 的逆變換.

現在我們已經將系數表達式轉換為點值表達式，并且計算出卷積的點值，考慮怎么快速通過點值還原出系數表達式. 由于單位根具有周期性，不妨帶入 $-\omega_n^k$ 試著計算一下. 具體的，設對 $A(x)$ 進行 DFT 之后得到的點值表示為

\[y_0,y_1,y_2,\cdots,y_{n-1} \]

構造多項式

\[F(x)=y_0+y_1x^1+y_2x^2+\cdots+y_{n-1}x^{n-1} \]

帶入點值

\[-\omega_n^0,-\omega_n^1,-\omega_n^2,\cdots,-\omega_n^{n-1} \]

計算一番

\[\begin{aligned} F(-\omega_n^k)&=\sum_{i=0}^{n-1}y_i\omega_{n}^{-ki}\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j\left(\omega_n^i\right)^j\omega_{n}^{-ki}\\ &=\sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}\left(\omega_n^{j-k}\right)^i\\ \end{aligned} \]

根據求和引理，僅當 $j-k=0$ 時右式值為 $n$，其余項全為 $0$. 所以最后得到：

\[F(-\omega_n^k)=a_k\cdot n \]

我們只需要仿照 DFT，帶入相反的點值，得到的結果再除以 $n$ 就可以在同樣 $O(n\log n)$ 的時間復雜度把點值表達式還原成系數表達式了.

蝴蝶變換

上述算法可以使用遞歸分治簡單實現，但是由于涉及三角函數、虛數、遞歸等等常數很大. 考慮尋找下標變換的規律：

\[\{x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7\}\\ \{x_0,x_2,x_4,x_6\},\{x_1,x_3,x_5,x_7\}\\ \{x_0,x_4\},\{x_2,x_6\},\{x_1,x_5\},\{x_3,x_7\}\\ \{x_0\},\{x_4\},\{x_2\},\{x_6\},\{x_1\},\{x_5\},\{x_3\},\{x_7\}\\ \]

由于每次每組的都按照組內序號的奇偶性再分組，可以觀察到：第 $i$ 輪分組從低到高第 $i$ 位為 $0$ 的會被分到左邊的組，為 $1$ 的會被分到右邊的組.

可以發現，若有 $2^m$ 個數進行遞歸分治，下標為 $2^{m-1}$ 的最后總是會排到下標為 $1$ 的位置，下標為 $2^{m-2}$ 的最后總是會排到 $2$ 的位置. 一個事實是每個下標最終的位置是最初下標的二進制位對稱翻轉得到的，也就是 $m$ 位二進制下標經過變換會得到

\[(b_mb_{m-1}b_{m-2}\cdots b_1)_2\rightarrow (b_1b_{2}b_{3}\cdots b_m)_2 \]

所以我們可以預處理變換數組，會大大減小代碼的常數.

2025.7.17 生成函數：ODF 與 EGF

普通生成函數 OGF

我們定義序列 $<a_0,a_1,a_2\cdots>$ 的普通生成函數 $A(x)$ 為形式冪級數

\[A(x)=\sum_{n\ge0}a_nx^n \]

同時 $A(x)$ 的系數 $a_n$ 寫作

\[a_n=[x^n]F(x) \]

依據定義，$A(x)$ 實際上是一個有無窮項的多項式，而 $a$ 既可以是又窮序列也可以是無窮序列.

基本運算

依據多項式的基本運算，對于 OGF $A(x),B(x)$ 也有

\[A(x)\pm B(x)=\sum_{n\ge0}a_nx^n\pm \sum_{n\ge0}b_nx^n =\sum_{n\ge0}(a_n\pm b_n)x^n \]

\[A(x) B(x)=\sum_{n\ge0}\sum_{i+j=n}a_ib_jx^n=\sum_{n\ge0}\sum_{i=0}^na_ib_{n-i}x^n \]

其中生成函數 $A(x),B(x)$ 的卷積定義就定義為 $A(x)B(x)$。卷積有著非常重要的組合意義，我們將在下文進一步探討.

OGF 系數的左移和右移直接對應下標的左移右移，也就是除以或乘以一個 $x$.

封閉形式

生成函數的一大特點就是其通常具有形式簡單的封閉形式，這樣可以使化簡變得更加輕松.

一般地，生成函數的封閉形式就是利用其系數和項數無窮的性質把其轉換為有限項的恒等形式。譬如 $<1,1,1,\cdots>$ 的普通生成函數 $F(x)$ 有封閉形式

\[F(x)=\sum_{n\ge0}x^n={1\over 1-x} \]

具體的推導我們發現 $F(x)x$ 對應序列 $<0,1,1,\cdots>$，所以有

\[xF(x)+1=F(x)\iff F(x)={1\over1-x} \]

類似地，等比數列 $<1,p,p^2,\cdots>$ 的生成函數 $F(x)$ 有封閉形式

\[F(x)=\sum_{n\ge0}p^nx^n=F(x)px+1\iff F(x)={1\over1-px} \]

值得一提的是，由于封閉形式與形式冪級數是恒等的，所以一些對于形式冪級數的操作也可以很直觀地反映在封閉形式上，遇到時要靈活應對，如

\[c\cdot F(x)=\sum_{n\ge0}cp^nx^n={c\over1-px} \]

提取系數

對于已知的封閉形式，我們可以嘗試提取系數來反向得到序列.
我們將以斐波那契數列的 OGF 為例來介紹提取系數的方法之一——待定系數法.

考慮斐波那契數列 $a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}(n>1)$，觀察到

\[\begin{aligned} F(x)&=a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4+\cdots\\ xF(x)&=\ \ \ \ \ \ \ \ +a_0x^1+a_1x^2+a_2x^3+a_3x^4+\cdots\\ x^2F(x)&=\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +a_0x^2+a_1x^3+a_2x^4+\cdots\\ \end{aligned} \]

根據遞推式，發現補上 $xF(x),x^2F(x)$ 的前面幾項就可以相加直接得到 $F(x)$. 所以 $F(x)$ 有封閉形式

\[xF(x)+x^2F(x)-a_0+a_1x+a_0=F(x)\iff F(x)={x\over1-x-x^2} \]

考慮用一定的形式來設出系數，比如

\[{A\over1-ax}+{B\over1-bx}={x\over1-x-x^2} \]

注意兩邊必須是齊次的.
接下來通分、根據系數恒等列出方程、求解方程，得到

\[{A-Abx+B-aBx\over(1-ax)(1-bx)}={x\over1-x-x^2} \]

\[\begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases} \]

\[\begin{cases} A={1\over\sqrt5}\\ B=-{1\over\sqrt5}\\ a={1+\sqrt5\over2}\\ b={1-\sqrt5\over2} \end{cases} \]

上面我們假設的封閉形式是等比數列之和，所以我們就可以帶入得到

\[F(x)={x\over1-x-x^2}=\sum_{n\ge0}{1\over\sqrt5}\Big(\Big({1+\sqrt5\over2}\Big)^n-\Big({1-\sqrt5\over2}\Big)^n\Big) \]

我們就得到了斐波那契數列的通項公式.

組合意義

OGF 卷積的組合意義是把物品組合起來，可以用來解決無標號的計數問題.

指數生成函數 EGF

定義

一個序列 $a_i$ 的指數生成函數定義為 $\sum \limits_{i\ge0}{a_i\over i!}x^i$，也就是在 OGF 的基礎上除以了 $i!$ .

常見級數與基本運算

序列 $\langle 1,1,\cdots,1\rangle$ 的指數生成函數是

\[\sum\limits_{i\ge0}{x^i\over i!} \]

會發現這其實是 $e^x$ 的泰勒展開（這也是名稱中“指數”的由來）.

還有一些常見的序列的封閉形式：

\[\langle1,-1,1,-1\cdots\rangle\Rightarrow e^{-x}\\ \langle c^0,c^1,c^2,\cdots\rangle\Rightarrow e^{cx}\\ \langle1,0,1,0,1\cdots\rangle\Rightarrow {e^x+e^{-x}\over2}\\ \langle1,a^{\underline 1},a^{\underline 2},a^{\underline 3},\cdots\rangle\Rightarrow {(1+x)^a}\\ \]

EGF 的卷積，根據定義展開可得：

\[A(x)\cdot B(x)=\sum_{n\ge0}\sum_{i=0}^n{n\choose i}a_ib_{n-i}x^n \]

而 EGF 系數的左移，右移分別對應多項式求導，積分. 根據定義式易得，在這里留給讀者自己證明.

組合意義

EGF 卷積的組合意義是物品的排列，可以解決有標號的計數問題.

而對組合對象（$x,F(x)$ 等等）求 EGF，根據上文，展開后就是對組合對象求 exp. 所以我們也可以說 exp 的組合意義是有標號物品的排列.

2025.7.18 線段樹歷史最值、區間取最值操作

區間歷史最值操作

可以先考慮歷史最大值怎么做. 類似于線段樹板子的，我們希望用某種 $tag$ 來對其進行維護.

那么考慮歷史最大值什么時候會發生變化. 現在我們已經維護了區間加法標記，隨著加法操作不斷進行，設現在的加法標記 $t_1=k$，發現：

$k>0$，歷史最大值會增加.
$k\le0$，歷史最大值不會改變.

然而當我們查詢時，歷史最大值實際上是上次查詢之后的 $\max\{k\}$. 也就是說我們需要額外維護一個 $t_2$ 來存 $t_1$ 的最大值. 下傳時，將 $t_2$ 更新給歷史最值即可. 這就是區間歷史最值的維護.

區間最值操作

注意：這個操作涉及到一些均攤、勢能分析技巧. 如果沒聽說過就感性理解.

這個操作最困難的點就在于它作用于很多值不同的數上，每種值的變化量不同，每種值受到作用的數還不止一個，并且限定了作用范圍.

于是我們不妨來思考更加簡易的操作：

如果區間取 $\min$ 只對最大值生效怎么做？那么區間中的每個最大值都減去了一個確定的數，我們只用維護區間最大值與區間最大值的個數即可.
只對最大值生效的條件是什么？我們不妨設區間對 $x$ 取 $\min$，那么一個充要的條件則是 $x$ 小于區間最大值，大于區間嚴格次大值. 區間次大值的維護也并不困難，但是 $x$ 如果不直接滿足這個條件應該怎么做呢？一個不難證明的性質是隨著線段樹向下遞歸，最大值和次大值是單調不增的，所以查詢時向下遞歸同樣也是單調不增的. 所以我們就可以在符合條件時向下遞歸，直到 $x$ 滿足上述條件就可以直接根據最大值的個數來進行修改了.

但是這樣看起來十分的暴力，為什么能夠保證復雜度正確呢？根據勢能分析，單獨的區間取最值按照上面的方法是均攤 $O(n\log n)$ 的，而區間取最值同時維護區間加的均攤復雜度為 $O(n\log^2 n)$，非常的優秀. 證明用到的一些關鍵性質是最值個數單調不增以及線段樹高 $O(\log n)$. 具體證明詳見吉如一老師的集訓隊論文.

具體實現涉及大量分討，但是根據定義還是不難理解的，多寫寫熟練就好.

2025.7.21 李超線段樹

線段樹上維護若干一次函數在線段樹每個區間中點處的最值（有點像凸殼），支持直線（線段）插入. 直線插入時間復雜度 $O(\log n)$，是在線段樹上搜索的復雜度. 線段插入時間復雜度 $O(\log^2 n)$，因為要拆分成 $O(\log n)$ 個區間分別遞歸.

考慮加入一條直線 $f(x)$，設線段樹上每個區間維護的線段并起來為 $g(x)$. 首先考察整個區間中點 $mid$ 哪個函數更優，分類討論：

若 $f(x)$ 更優，將其與這一段的 $g(x)$ 交換.

此后進行一次判斷，若區間 $l=r$ 不再能二分就結束遞歸，否則繼續判斷：

若左端點 $f(x)$ 更優，說明左區間存在可能更新的 $g(x)$，所以遞歸到左兒子繼續更新.
若右端點 $f(x)$ 更優，說明右區間存在可能更新的 $g(x)$，所以遞歸到右兒子繼續更新.

上述算法用于維護一條直線的插入. 如果插入一條線段，則需要像線段樹區間修改操作那樣分出每個區間分別進行上述操作.

核心代碼：

struct lct{
	int tr[maxn];
	inline ld f(int x, int id) {return (ld)l[id].k * x + l[id].b;}
	inline bool eq(ld x, ld y) {return x - y <= eps && y - x <= eps;}
	inline bool cmp(int u, int v, int x) {//u 是否比 v 優 
		ld a = f(x, u), b = f(x, v);
		return a > b || (eq(a, b) && u < v);
	}
	inline void upd(int u, int l, int r, int p) {
		int mid = l + r >> 1;
		if(cmp(p, tr[u], mid)) swap(tr[u], p);//遞歸修改 
		if(l == r) return;
		if(cmp(p, tr[u], l)) upd(ls, l, mid, p);
		if(cmp(p, tr[u], r)) upd(rs, mid + 1, r, p);
		return;
	} 
	inline void add(int u, int l, int r, int ql, int qr, int p) {
		if(ql <= l && r <= qr) return upd(u, l, r, p), void(0);
		int mid = l + r >> 1;
		if(ql <= mid) add(ls, l, mid, ql, qr, p);
		if(mid < qr) add(rs, mid + 1, r, ql, qr, p);
		return;
	}
	inline int ask(int u, int l, int r, int p) {
		if(l == r) return tr[u];
		int mid = l + r >> 1, res = tr[u], tmp;
		if(p <= mid) tmp = ask(ls, l, mid, p);
		else tmp = ask(rs, mid + 1, r, p);
		return (cmp(tmp, res, p) ? tmp : res);
	}
} t;

2025.7.22 長鏈剖分

最好有重鏈剖分的基礎再來學這個，否則你應當先學習重剖.

類似于重鏈剖分以子樹大小最大的作為重兒子，長鏈剖分以兒子中擁有最長鏈的為重兒子. 所以我們仿照重剖，可以寫出兩個核心 dfs 函數.

int len[maxn], son[maxn], fa[maxn];
inline void dfs1(int u, int f) {
	fa[u] = f, len[u] = 1;
	for(int i = head[u], v; i; i = e[i].nxt) {
		v = e[i].v; if(v == f) continue;
		dfs1(v, u);
		if(len[v] + 1 > len[u]) len[u] = len[v] + 1, son[u] = v;
	} return;
}
int tp[maxn];
inline void dfs2(int u, int t) {
	tp[u] = t; if(son[u]) dfs2(son[u], t);
	for(int i = head[u], v; i; i = e[i].nxt) {
		v = e[i].v; if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	} return;
}

上述代碼維護了 len[u] 表示以 $u$ 起始的鏈的長度.

那么長鏈剖分有什么用呢？我們來看看它的一些性質.

所有長鏈長度之和是 $O(n)$ 的. 該命題相當于所有長鏈無交，根據定義這是恒成立的.
任意節點 $u$ 的 $k$ 級祖先所在的長鏈長度一定大于等于 $k$. 設 $u$ 的 $k$ 級祖先是 $v$，分類討論. 如果 $u$ 和 $v$ 在同一條長鏈顯然成立；如果 $u$ 和 $v$ 不在同一條長鏈上，假設 $v$ 所在長鏈長度小于 $k$，但是 $v\rightarrow u$ 這條鏈長度已經為 $k$，所以長鏈應該延申到 $u$，這與 $u,v$ 不在同一條長鏈相矛盾，故假設不成立.
任意節點 $u$ 可以經過 $O(\sqrt n)$ 條輕邊到達根節點. 該命題相當于跳 $O(\sqrt n)$ 次長鏈頂可以到達根節點. 根據第一條性質，我們會發現向上跳長鏈的長度是嚴格單調遞增的，否則一定可以通過調整得到更長的鏈作為長鏈. 故跳的長鏈長度之和至少是 $1+2+\cdots=n$，會發現長鏈條數是 $O(\sqrt n)$ 的.

2025.7.25 kmp 與 manacher

KMP

可以 $O(n)$ 求字符串每個前綴的最長前后綴.

border

字符串一對相等的真前綴和真后綴叫做 border.

KMP 求的其實就是每個前綴的最長 border.

實現

記位置 $i$ 的最長 border 為 $fail_i$.

考慮雙指針維護，$j$ 記錄前綴的匹配，$i$ 記錄后綴的匹配. 我們在之前 $j$ 匹配 $i-1$ 的基礎上，要找到一個 $j$ 匹配 $i$. 對于每個 $i$，如果 $s_i$ 與 $s_{j+1}$ 不等，那么 $j$ 就要跳到一個 $s_{j'}=s_{i-1}$ 的最大位置，這樣一定優. 然后我們會發現這個 $j'$ 就是 $fail_j$ 的定義，所以直接不斷地令 $j=fail_j$ 重復上面的判斷即可.

其實既可以求字符串自己與自己的最長 border 也可以求兩個串的最長 border，區別只是后者額外再匹配一遍另一個串.

for(int i = 2, j = 0; i <= m; i++) {// fail[1] 無價值 
	while(j && s2[j + 1] != s2[i]) j = fail[j];
	if(s2[j + 1] == s2[i]) j++;
	fail[i] = j; 
}
for(int i = 1, j = 0; i <= n; i++) {
	while(j && s2[j + 1] != s1[i]) j = fail[j];
	if(s1[i] == s2[j + 1]) j++;
	if(j == m) cout << i - j + 1 << endl, j = fail[j];
}

注意 $fail_1=1$ 是無價值的，而且這樣會讓程序陷入死循環.

時間復雜度

挪動 $i$ 顯然是線性的，但為什么 $j$ 跳的次數是 $O(n)$ 的？

其實因為 $j$ 跳一次 $fail_j$ 至少減少 $1$，但是一次匹配上最多增加 $1$，這就保證了 $j$ 一定不會跳超過 $O(n)$ 次. 所以總復雜度就是 $O(n)$ 的.

Manacher

可以 $O(n)$ 求所有回文子串的不同位置.

思路和 Z 函數幾乎一樣，是拿之前的回文信息來更新后面的回文信息.

特殊處理

回文串有奇回文和偶回文兩種，也就是對稱點可能是字符也可能是字符之間的空隙. 如果分類討論的話非常地不優美，所以我們有一個聰明的解決辦法：

在每個字符之間包括頭尾插入一個特殊字符如 #
最開頭插入另一個特殊字符如 ~

這樣既可以避免越界也可以讓所有最長回文串都只能是奇回文. 而且原串最長回文子串長度就是新串最長回文半徑長度減去 $1$.

s[0] = '~', s[1] = '#';
for(int i = 1; i <= n; i++) s[++tot] = c[i], s[++tot] = '#';

實現

考慮維護每個節點可以拓展的最大半徑 $d_i$，維護最遠的 $(mid,r)$ 使得令 $l=2\times mid-r$，有 $s_{l\cdots r}$ 是一個回文中心為 $mid$ 的最長回文串. 回文串對稱的性質告訴我們，你要求一個 $i\in[mid,r]$ 的 $d_i$，可以在這個極長回文串的對稱位置的 $d_{l}$ 基礎上更新來. 具體的，與 Z 函數類似有：

$i \in [mid,r]$
$d_{l}\le r-i+1$

符合上述要求就可以直接 $d_i=d_l$ 了. 如果不行就在 $d_i=\max(1,r-i+1)$ 基礎上暴力往兩邊拓展，并更新 $(mid,r)$ 就好了.

for(int i = 1, mid = 0, r = 0; i <= tot; i++) {
	if(i <= r && d[2 * mid - i] < r - i + 1) d[i] = d[2 * mid - i];
	else {
		d[i] = max(1, r - i + 1);
		while(s[i + d[i]] == s[i - d[i]]) d[i]++;
		if(i + d[i] > r) r = i + d[i] - 1, mid = i;
	} 
}

2025.8.18 差分約束

對 $n$ 組形如 $x_i+w\ge x_j$ 的不等關系求最大/最小解或報告無解，考慮用最短路的三角不等式 $dis_u+w\ge dis_v$ (最終狀態) 來類比刻畫.

考慮 $u\rightarrow v$ 屬于是最短路當且僅當 $dis_u+w\ge dis_v$，于是 $x_i+w\ge x_j$ 就應該連 $i\rightarrow j$ 邊權為 $w$ 的有向邊. 加上虛點向各點連邊權為 $0$ 的邊，跑全源最短路，原圖存在負環則無解. 可以證明，這樣跑最短路得到的 $dis_i$ 是 $x_i$ 的合法最大解：考慮記任意一條從起點出發到 $i$ 的路徑邊權和為 $S$，根據邊的定義則一定有 $x_i<S$，所以 $x_i$ 的上界就是 $S$ 的最小值，即 $dis_i$.

類似的對于形如 $x_i+w\le x_j$ 的不等關系可以通過連 $i\rightarrow j$，邊權為 $w$ 的邊跑最長路得到 $x_i$ 的下界.

一些常用的轉化連邊：

$x_i-x_j\le k$，即 $x_j+k\ge x_i$，連邊 $j\rightarrow i$，邊權 $k$.
$x_i-x_j\ge k$，即 $x_j-k\ge x_i$，連邊 $i\rightarrow j$，邊權 $-k$.
$x_i-x_j= k$，即 $x_j-x_i\le k\wedge x_i-x_j\ge k$，連邊 $j\rightarrow i$，邊權 $k$，$i\rightarrow j$，邊權 $-k$.

posted @ 2025-07-11 15:19 Ydoc770 閱讀(18) 評論(1) 收藏舉報

刷新頁面返回頂部

Ydoc770