2025.7-2025.8 做題記錄

7.1 - 7.11

復習段考 + 段考 + 講評課

7.12

模擬賽

7.12 T1 - 規(guī)則制定 (單調棧)

所有區(qū)間的區(qū)間和之和容易求，拆到每個元素上即可

下面考慮如何求所有區(qū)間的最大值之和

若區(qū)間內有多個最大值，考慮將貢獻放到最靠前的最大值上

求出 \(\text{lmax}_i\) 表示 \(i\) 前最靠后的滿足 \(a_j \ge a_i\) 的 \(j\)，\(\text{rmax}_i\) 表示 \(i\) 后最靠前的滿足 \(a_j > a_i\) 的 \(j\)

\(a_i\) 作為最大值的貢獻次數(shù)即為 \([\text{lmax}_i, \text{rmax}_i]\) 中長度 \(\ge 3\) 的區(qū)間個數(shù)

實現(xiàn)時可以用單調棧 \(O(n)\) 維護

7.12 T2 - 作文批改 (隨機權 + 和 Hash)

考慮星戰(zhàn)的做法，給字符 \(c\) 賦隨機權值 \(v_c\)，和哈希判斷是否相同

不過這里有個"出現(xiàn)次數(shù)為 \(k\) 倍"，因此考慮先求出 \(t\) 的哈希值 \(B\) (不取模)，以 \(B\) 為模數(shù)維護 \(s\) 的前綴哈希值 \(pre_i\)

此時子串 \(s_{[l, r]}\) 符合要求等價于 \(pre_r = pre_{l-1}\)

由生日悖論，值域為 \(V\) 時出現(xiàn)沖突的期望抽樣次數(shù)為 \(O(\sqrt V)\)；此處抽樣次數(shù)為 \(10^7\)，需保證 \(B \ge 10^{14}\)

實現(xiàn)細節(jié)：

• 可以根據(jù) \(|t|\) 動態(tài)調整隨機權范圍
• umap 常數(shù)太大，直接 sort 后雙指針比 umap 快

7.12 T3 - 賽道設計 (Adhoc)

可以通過手玩猜出 \(|R-L| \in [3, 5]\) 的結論 (起點也可以視作拐點)

下面給出嚴謹證明

設有 \(m\) 個拐點，則賽道為 \(m\) 邊形，每個內角均為 \(90^{\circ}\) 或 \(270^{\circ}\)，內角和為 \((m-2) \times 180^{\circ}\)

由于所有 \(L / R\) 對應的內角只能均為 \(90^{\circ}\) 或 \(270^{\circ}\)，且兩者對應度數(shù)不同，可得 (不妨設 \(L\) 對 \(90^{\circ}\) )

\(L \times 90^{\circ} + R \times 270^{\circ} = (L+R-2) \times 180^{\circ}\)

整理即得 \(L-R = 4\)

由于連續(xù)的 \(LR / RL\) 不會帶來方向上的變化，可先將其刪去；調整起點，最后一定能剩下 \(LLLL / RRRR\)

這個構造是簡單的；之后重新往里添加 \(LR / RL\) 的過程相當于選兩個點，將路線從直線改成三折

每次重新調整其他所有點的位置可以做到相對位置不變；時間復雜度 \(O(Tn^2)\)

實現(xiàn)咕咕咕

LOJ6538 烷基計數(shù) 加強版 加強版 (群論 + 生成函數(shù) + 牛迭)

見群論基礎 - 學習筆記 Blog

P6597 烯烴計數(shù) (群論 + 生成函數(shù) + 牛迭)

見群論基礎 - 學習筆記 Blog

P6598 烷烴計數(shù) (群論 + 生成函數(shù) + 牛迭)

見群論基礎 - 學習筆記 Blog

7.13

開擺 + 補 whk

7.14

P3391 【模板】文藝平衡樹

本題中，我們并不關心平衡樹每個節(jié)點具體的值是否滿足 BST 的性質

此處平衡樹的每個節(jié)點對應原序列的下標，換句話說，我們按照下標建樹

考慮如何刻畫翻轉操作；若我們能夠分裂出 \([l, r]\) 對應的子樹，將每層的節(jié)點全部左右調換即可 (可理解為值換了，對應下標不換)

直接換顯然會 TLE；考慮線段樹懶標記的思想，給要全部調換的子樹的根打 tag，用到的時候再真正交換兒子

現(xiàn)在考慮如何分裂出 \([l, r]\) 對應的子樹

注意到序列下標始終滿足 BST 的性質，考慮按排名分裂的思想，只不過此處是按子樹大小分裂；具體的：

1. 分裂出 \([1, l-1]\) 與 \([l, n]\) (按大小為 \(l-1\) 分裂)
2. 將 \([l, n]\) 分裂為 \([l, r]\) 與 \([r+1, n]\) (按大小為 \(r-l+1\) 分裂)

P3835 【模板】可持久化平衡樹

仍然套路的考慮記錄每個版本的根，復制所有修改過的節(jié)點

具體的，為避免直接修改歷史版本的值，在每次 split 與 merge 時對將進行分裂 / 合并的節(jié)點復制一份再操作即可

實現(xiàn)時，無須復制遞歸處理的另一側 (遞歸處理子樹時自然會復制的)

P5338 [TJOI2019] 甲苯先生的滾榜 (平衡樹)

把 int 換成結構體，"修改通過題數(shù)和罰時"可變成先刪除后插入

注意人的編號無法直接和 Treap 中的值建立聯(lián)系，需要開個輔助數(shù)組

P4146 序列終結者 (平衡樹 - 區(qū)間加 + 區(qū)間翻轉 + 區(qū)間 max)

考慮在 Treap 上的節(jié)點維護當前下標的值 + 子樹對應區(qū)間的最大值

區(qū)間翻轉仍然通過打 tag 維護，區(qū)間加相當于又多了個 tag；修改時直接分裂出區(qū)間打上 tag 即可

注意，打 tag 的順序是：

1. 打 tag 前做好當前節(jié)點的修改
2. 給當前節(jié)點打上 tag
3. pushdown 時做好兒子節(jié)點的修改，把 tag 傳到兒子節(jié)點上

為什么不能在 pushdown 時只做當前節(jié)點的修改，pushdown 兒子時再修改兒子？

因為 merge 時實際上非遞歸側的兒子不會被 pushdown，需要在 pushdown 當前節(jié)點時就處理好兒子節(jié)點的信息

P3765 總統(tǒng)選舉 (平衡樹 + 隨機化 - 帶修絕對眾數(shù))

先考慮如何判斷區(qū)間 \([l, r]\) 是否存在絕對眾數(shù)

考慮隨機化；隨機 \(\text{lim}\) 次，每次隨出一個位置 \(i\)，判斷 \(a_i\) 在 \([l, r]\) 中出現(xiàn)次數(shù)是否超過一半

這樣單次失敗概率是 \(\displaystyle \frac{1}{2}\)，\(\text{lim}\) 次就是 \(\displaystyle \frac{1}{2^\text{lim}}\)，大概可以接受

那么問題在于如何快速統(tǒng)計 \(a_i\) 在 \([l, r]\) 中的出現(xiàn)次數(shù)

先考慮不帶修怎么做

對每個值 \(v\) 開 vector 記錄其出現(xiàn)位置 (顯然有序)，查詢時直接二分即可

帶修相當于要支持刪除 + 插入，二分可以變成查排名；那么對每個值 \(v\) 開一棵平衡樹即可

實現(xiàn)時可以取 \(\text{lim} = 13\)

P2596 [ZJOI2006] 書架 (平衡樹 - 下標移動)

操作 \(4\) 是根據(jù)值查排名，操作 \(5\) 是根據(jù)排名查值，明示平衡樹；問題在于我們沒辦法直接建立編號與位置的關系

考慮給每本書賦值 \(v\) 代表其相對位置大小 (由于是相對的，沒必要時刻連續(xù))

為建立編號與 \(v\) 的聯(lián)系，考慮開兩個 map，第一個從編號映射到 \(v\)，第二個從 \(v\) 映射到編號

接下來考慮每個操作：

• Top，從 map 中取出編號對應的 \(v\)，將 \(v\) 修改為全局編號最小值 \(-1\) 即可

  實現(xiàn)時可以維護全局編號最小值，"修改"就是刪除 + 插入

• Bottom，類似的，維護全局編號最大值，刪除 + 插入即可

• Insert，本質上是與前驅或后繼交換；注意到 Treap 上節(jié)點對應的 \(v\) 沒變，變的只有 \(v\) 與編號的對應關系

  從 map 中取出 \(v\)，查出前驅 / 后繼，將 map 上兩組對應關系交換即可

• Ask，從 map 中取出 \(v\)，根據(jù)值查排名即可

• Query，根據(jù)排名查值，最后通過 map 從 \(v\) 映射回編號即可

P2566 [SCOI2009] 圍豆豆 (區(qū)間DP + 計算幾何)

先考慮如何判斷點在多邊形內

由計算幾何知識，考慮從點引一條射線，若與多邊形交點個數(shù)為奇數(shù)則包含，反之不包含

此處多邊形的邊只能是水平 / 豎直的，為方便判斷，欽定每個點引射線的方向都是水平向右的

因此，在平行于射線 (水平方向) 移動時不計算交點，豎直移動時才計算

設 DP 狀態(tài) \(f_{x, y, S}\) 表示走到 \((x, y)\)，點的包含關系為 \(S\) 時的最短步數(shù)；其中，\(S_i\) 代表第 \(i\) 個點引出的射線與多邊形交點的奇偶性

接下來考慮如何計算 \(S\)

直接按"每經過一次點右邊的格子就算一次"的方式考慮是不可取的，因為每個格子有"進入"、"離開"兩次操作

注意到按同一方向 (均上 \(\rightarrow\) 下 / 均下 \(\rightarrow\) 上) 只應當被算一次，因此考慮從經過格子的兩個方向上統(tǒng)計；具體的：

• 當從上 \(\rightarrow\) 下進入格子時，統(tǒng)計 \(1\) 次

• 當從下 \(\rightarrow\) 上離開格子時，統(tǒng)計 \(1\) 次

  為什么這里是"離開"而非"進入"？因為要想形成多邊形，必然要跨過格子所在水平線，只有離開格子時才是真正跨過去

實現(xiàn)時可以枚舉起點，bfs 進行轉移，第二次走到起點時結束

初始狀態(tài)為 \(f_{x, y, 0} = 0\)；設 \(v_S\) 為 \(S\) 狀態(tài)包含的點的價值和，答案為 \(\max (v_S-f_{x, y, S})\)

時間復雜度 \(O(n^2m^22^D)\)

7.15

P3401 洛谷樹 (樹剖 + 拆位)

考慮如何維護子路徑 xor 和

注意到邊權 \(\le 2^{10}\)，考慮拆位，開 10 棵線段樹

考慮經典轉化，將路徑 xor 變?yōu)?strong>兩個根鏈 xor，維護每個點到根的 xor 值

記 \(cnt_0\) 為 \(u, v\) 間路徑中第 \(i\) 位為 \(0\) 的點的個數(shù)，\(cnt_1\) 為 \(u, v\) 間路徑中第 \(i\) 位為 \(1\) 的點的個數(shù)，貢獻即為 \(cnt_0 \times cnt_1 \times 2^i\)

那么維護區(qū)間中根鏈 xor 當前位為 \(0\) / \(1\) 的點的個數(shù)即可

對單點改，若 \((u, v)\) 更改后邊權的第 \(i\) 位與更改前不同，則相當于子樹區(qū)間 \(0\) / \(1\) 翻轉

綜上，上樹剖 + 支持區(qū)間加區(qū)間 \(0\) / \(1\) 翻轉區(qū)間和的線段樹即可

P2542 [AHOI2005] 航線規(guī)劃 (樹剖 - 刪邊求割邊個數(shù))

首先考察是樹怎么做

顯然，此時 \(u, v\) 間的割邊個數(shù)即為兩點樹上路徑中的邊的個數(shù)；這啟示我們給邊賦 \(1\)，做樹剖 + 路徑區(qū)間查

在樹的基礎上給 \(u, v\) 加邊，相當于讓兩點樹上路徑中的邊全部處于環(huán)中

此時這些邊不再產生貢獻，做路徑區(qū)間推平即可

綜上，上樹剖 + 支持區(qū)間加區(qū)間推平區(qū)間和的線段樹即可

P3676 小清新數(shù)據(jù)結構題 (樹剖 + 線段樹 - 區(qū)間加區(qū)間平方和)

首先考慮沒有換根怎么做

先求出每個點 \(i\) 初始的子樹大小 \(siz_i\)，維護 \(siz_i\) 的平方和

此時單點改只會對根鏈上的點的子樹大小產生影響，為路徑區(qū)間加

顯然，直接上支持區(qū)間加區(qū)間平方和的線段樹即可

接著考慮換根；對于這類操作，我們一般不真換，而是分析其在保持根不動的前提下帶來的變化

不妨設根換為點 \(u\)：

• 對點 \(u\) 的子樹中的點 \(v\)，貢獻不變
• 對點 \(u\)，從 \(siz_u^2\) 變?yōu)?\((\sum siz_i)^2\)
• 對非根鏈上的點 \(v\)，貢獻不變
• 對根鏈上的點 \(v\)，子樹大小減少了面向 \(u\) 的部分，增加了面向根的部分

不妨設 \(1, u\) 間路徑上的點為 \(1 = a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_k = u\)，點 \(i\) 原大小為 \(siz_i\)，新大小為 \(siz'_i\)，原答案為 \(t\)，則新答案為：

顯然有 \(siz'_{a_i} + siz_{a_{i+1}} = siz_1 = siz'_u\)，代入，可得

那么只需維護 \(t, siz_1\) 與根鏈路徑區(qū)間和即可；

綜上，仍然是上樹剖 + 支持區(qū)間加區(qū)間和區(qū)間平方和的線段樹即可

P5391 [Cnoi2019] 青染之心 (樹剖 - 末尾加 / 撤銷完全背包優(yōu)化空間)

操作序列實際上形成了一棵樹，add 相當于拼個兒子，erase 相當于回退到父親；要求所有根鏈的完全背包

暴力做法時空復雜度均為 \(O(qV)\)，空間上無法接受；考慮如何優(yōu)化

注意到若節(jié)點 \(u\) 的 DP 數(shù)組已經傳到每個兒子 \(v\) 上，其本身已經沒有用處了；因此考慮將某個兒子 \(v\) 的 DP 數(shù)組覆寫到 \(u\) 的數(shù)組上

結合樹鏈剖分，考慮令 \(v\) 為 \(u\) 的重兒子，最后處理 \(v\)，將其 DP 數(shù)組覆寫到 \(u\) 的數(shù)組上

每當我們 dfs 完一條根到葉子的鏈時，立刻回收空間，經過的輕兒子數(shù)是 \(\log\) 的，那么空間復雜度也是 \(\log\) 的

P5314 [Ynoi2011] ODT (樹剖 + 平衡樹維護輕兒子)

"第 \(y\) 小點權"明示我們使用平衡樹

考慮修改；暴力做法是把路徑上所有點的平衡樹全改一遍，顯然無法接受

考慮與上道題類似的策略，令 \(u\) 點的平衡樹維護其所有輕兒子的權值

路徑改時只會經過 \(\log\) 個輕兒子，只會改 \(\log\) 個平衡樹 (修改就是刪除 + 插入)，可以接受

查詢時，將點 \(u\) 的父親 + 重兒子插進平衡樹，查出答案，最后再刪掉即可

實現(xiàn)時還需要維護一個線段樹 / 樹狀數(shù)組查每個點本身的點權

時間復雜度 \(O(n \log^2 n)\)

7.16

BZOJ P3648 寢室管理

AGC001C - Shorten Diameter

P7215 [JOISC 2020] 首都

7.17

P5642 人造情感（emotion） (樹上路徑最大獨立集 DP)

先假設我們可以快速求出 \(W(S)\)

對 \(f(u, v)\)，由于加入 \(\text{path}(u, v)\) 后 \(W\) 變大，顯然 \(\text{path}(u, v)\) 必然被選，其上的點均不能被占用

考慮將 \(\text{path}(u, v)\) 上的點及其所連的邊全部刪去以刻畫"不能被占用"；記刪去路徑后形成的若干樹為 \(T_1, T_2, \cdots, T_k\)，完全包含于 \(T_i\) 中的路徑集為 \(S_i\)，可得 \(w = W(S)-\sum_{i=1}^{k} W(S_i)\)

不妨令 \(1\) 為根；更進一步，易得刪去路徑后剩下的樹只能是：

• 原來以某個點為根的子樹
• 整棵樹刪去以某個點為根的子樹后得到的樹 (子樹的補)

綜上，考慮設計狀態(tài)刻畫"完全包含于某個子樹 / 子樹的補中的路徑集的 \(W\) 值"

為求子樹中的答案，我們令：

• \(f_u\) 表示僅考慮 \(u\) 子樹的答案
• \(s_u\) 表示僅考慮 \(u\) 子樹，且強制不占用 \(u\) 的答案

對初始值，考慮葉子 \(l\)，有 \(f_l = \max_{u_i = l, v_i = l} w_i\) 且 \(s_l = 0\)；我們從下向上轉移：

• \(s_u \leftarrow \sum f_v\)，其中 \(v\) 是 \(u\) 的兒子

• $ f_u \leftarrow s_u + \max { w_i-\sum_{k \in \text{path}(u_i, v_i)} (f_k-s_k) }$，其中 \(\text{lca}(u_i, v_i) = u\)

  解釋：考慮先強制不選 \(u\)，再拼上一條經過 \(u\) 的路徑 (因此將每條路徑掛在其兩端點的 lca 上)；這條路徑上的點都不能被占用，因此對路徑上的每個點 \(k\)，減去 \((f_k-s_k)\) 表示將 \(k\) 點從可選可不選調整至必須不選的代價

  注意到，若 \(k\) 原本就不選，必有 \(f_k = s_k\)；若 \(k\) 原本選，代價就是 \(f_k-s_k\)，正確性沒有問題

  那么 \(k\) 點的代價 \(f_k-s_k\) 是否會被重復計算？其實也不會，若路徑經過 \(k \rightarrow v \rightarrow u\)，若之前 \(v\) 點已經考慮了強制不選 \(k\) 的代價，在 \(u\) 點轉移時將 \(f_v\) 改為 \(s_v\) 時會撤去這一代價，最終也只會在 \(k\) 處算一次

  考慮如何維護 \(\sum_{k \in \text{path}(u_i, v_i)} (f_k-s_k)\)

  其實就是單點加 + 鏈求和，樹剖固然可做，不過樹狀數(shù)組維護根鏈可以少個 \(\log\)

  形式化的，設 \(i\) 的子樹的 \(\text{dfn}\) 區(qū)間為 \([\text{dfn}_i, \text{bottom}_i]\)：

  • 對 \(i\) 單點加變?yōu)樵?\(\text{dfn}_i\) 加，在 \(\text{bottom}_i+1\) 減 (轉化為子樹加，差分了一下)
  • 對 \(i\) 查詢相當于查 \([1, \text{dfn}_i]\)

容易發(fā)現(xiàn)，\(f_1 = W(S)\)

為求子樹的補的答案，我們令 \(g_u\) 表示 \(u\) 子樹的補的答案

在求出 \(g_u\) 后，我們給掛在 \(u\) 上的每條路徑 \(\text{path}(u_i, v_i, w_i)\) 賦新權 \(w'_i = w_i+s_u-\sum_{k \in \text{path}(u_i, v_i)} (f_k-s_k)+g_u\)，表示選擇該條路徑時，考慮子樹內代價 + 子樹外貢獻的值 (即全局貢獻的值)

對初始值，考慮根 \(1\)，顯然有 \(g_1 = 0\)；我們從上向下轉移，從 \(u\) 轉移到兒子 \(v\) 時：

• 若 \(u\) 未被占用，有 \(g_v \leftarrow g_u+s_u-f_v\)

  解釋：\(s_u-f_v\) 表示考慮 \(u\) 除兒子 \(v\) 的其他兒子的貢獻

• 若 \(u\) 被形如 "\(u\) 的后代 \(\rightarrow u \rightarrow\) \(u\) 的祖先" 方向的路徑占用，令這樣的路徑的權 (新權) 的 max 為 \(w'\)，有 \(g_v \leftarrow w'-f_v\)

  由定義，這樣的路徑有且僅有一個端點是 \(u\) 的后代，且這個端點不是 \(v\) 的后代

  考慮如何維護這樣的路徑

  由于轉移順序是從上到下，轉移到 \(g_v\) 時已經經過了 \(v\) 的所有祖先；因此考慮在每個點 \(p\) 處理掛在 \(p\) 上的路徑對其后代的貢獻

  設路徑為 \(\text{path}(u_i, v_i, w'_i)\)，將考慮 \(p\) 的兒子 \(q\) 的方向的轉移；若 \(u_i\) 或 \(v_i\) 是 \(q\) 的后代 (不妨設此處 \(u_i\) 是 \(q\) 的后代)，則將 \(w'_i\) 插入 \(\text{dfn}_{u_i}\)，對 \(q\) 的后代 \(s\) 及其兒子 \(t\)，從 \(s\) 轉移到 \(t\) 時查詢"是 \(s\) 的后代且不是 \(t\) 的后代"的 \(\text{dfn}\) 區(qū)間的 max 即可

  形式化的，設 \(i\) 的子樹的 \(\text{dfn}\) 區(qū)間為 \([\text{dfn}_i, \text{bottom}_i]\)，查詢 \([\text{dfn}_s, \text{dfn}_t-1] \bigcup [\text{bottom}_t+1, \text{bottom}_s]\) 中的 max 即可

  那么只需支持單點改 + 區(qū)間查 max 的線段樹即可

  實現(xiàn)時千萬注意順序，先求出所有兒子 \(v\) 的 \(g_v\)，再將掛在 \(u\) 上的路徑插入線段樹，再遞歸求解 \(v\) 的子樹

• 若 \(u\) 被形如 "\(u\) 的后代 \(\rightarrow u \rightarrow u\) 的后代" 方向的路徑占用，同理令這樣的路徑的權的 max 為 \(w'\)，有 \(g_v \leftarrow w'-f_v\)

  設路徑為 \(\text{path}(u_i, v_i, w'_i)\)，顯然有 \(\text{lca}(u_i, v_i) = u\)，換句話說，這些路徑都是掛在 \(u\) 上的

  此時直接將這些路徑排序，找到第一條滿足 \(u_i\) 不是 \(v\) 的后代且 \(v_i\) 也不是 \(v\) 的后代的路徑即可

  每條路徑最多浪費兩次訪問 (\(u_i\) 是 \(v\) 的后代 / \(v_i\) 是 \(v\) 的后代)，時間復雜度沒問題

現(xiàn)在考慮如何求 \(f(u, v)\) (這里只看 \(W(S)\) 減去的東西)

對路徑 \(\text{path}(u, v)\)，非 lca 的每個點的每個兒子的子樹 (不包含路徑上的點) 被分離出來；同時，lca 子樹的補也會被分離出來

簡單容斥下，有：

• 對不為 lca 的點 \(u\)，貢獻為 \(s_u-f_u\)
• 對為 lca 的點 \(u\)，貢獻為 \(g_u+s_u\)

求這個應當是簡單的

時間復雜度 \(O(n \log n)\)

7.18

CF566C - Logistical Questions (觀察性質 + 點分治 - 移動重心)

7.19

P8250 交友問題 (圖上根號分治)

CF2101E - Kia Bakes a Cake (點分治優(yōu)化 DP)

CF1270F - Awesome Substrings (根號分治)

7.20

開擺 + 補 whk

7.21

P4168 [Violet] 蒲公英 (分塊 - 維護塊間答案)

P3203 [HNOI2010] 彈飛綿羊 (分塊 - 維護跳出塊信息)

P10590 磁力塊 (分塊 - 維護塊內指針)

CF455D - Serega and Fun (分塊 - 維護 deque)

7.22

P2500 [SDOI2012] 集合 (圖上根號分治)

7.23

P1494 [國家集訓隊] 小 Z 的襪子 (莫隊)

CF852I - Dating (樹上莫隊)

\(O(n \log n) - O(1)\) lca

7.24

CF940F - Machine Learning (帶修莫隊)

7.25

P5903 【模板】樹上 K 級祖先 (長剖求 K 級祖先)

P3591 [POI 2015] ODW (長剖求 K 級祖先 + 根號分治)

CF1491H - Yuezheng Ling and Dynamic Tree (分塊 - 彈飛綿羊 Trick + 均攤)

7.26

講群論 + 調不出來題

7.27

P11527 [THUPC 2025 初賽] waht 先生的法陣 (分塊 - 彈飛綿羊 Trick + 均攤)

P2481 [SDOI2010] 代碼拍賣會 (數(shù)位 DP - 前后綴拆分 Trick + 循環(huán)節(jié))

CF708C - Centroids (換根 DP)

P6419 [COCI 2014/2015 #1] Kamp (換根 DP)

7.28

P3647 [APIO2014] 連珠線 (觀察性質 + 換根 DP)

不妨先令點 \(1\) 為根；容易發(fā)現(xiàn)，只存在 \(u - v - v'\) ( \(v \in \text{son}_u, v' \in \text{son}_v\) ) 與 \(v_1 - u - v_2\) ( \(v_1, v_2 \in \text{son}_u\) ) 兩種連藍鏈的結構

由題意，兩條藍鏈不能在非端點處相交；結構 \(1\) 中 \(u\) 可作為端點，結構 \(2\) 中 \(u\) 不能作為端點，這會給 DP 帶來很大麻煩

考慮觀察性質；紅線只能連接新珠子與已有珠子，而對于結構 \(2\)，\(u\) 一定是已有珠子；因此有：

• 不存在兩個結構 \(2\)，使得 \(u_1, u_2\) 無祖先后代關系

那么我們必然可以找到一個點 \(rt\)，使得以點 \(rt\) 為根時，所有結構 \(2\) 都變成結構 \(1\)

這啟示我們進行換根 DP

先考慮子樹內；令 \(f_{u, 0/1}\) 表示僅考慮 \(u\) 子樹，\(u\) 所在藍鏈長度為偶 / 奇的答案；轉移為：

• \(\displaystyle f_{u, 0} \leftarrow \sum_{v \in \text{son}_u} \max(f_{v, 0}, f_{v, 1}+w(u, v))\)，表示每個兒子可以選擇是否拼上點 \(u\)

• \(\displaystyle f_{u, 1} \leftarrow f_{u, 0} + \max_{v \in \text{son}_u} (f_{v, 0} + w(u, v) - \max(f_{v, 0}, f_{v, 1}+w(u, v)))\)，表示強行欽定一個兒子拼上點 \(u\)

  為輔助換根，此處套路地記錄 \(\max\) 的最大值 \(s_{u, 1}\) 與次大值 \(s_{u, 0}\)

初始值為對葉子 \(u\)，\(f_{u, 0} = 0\)，\(f_{u, 1} = -\infty\)

再令 \(dp_{u, v, 0/1}\) 表示從 \(u\) 子樹中挖去 \(v\) 子樹 (\(v \in \text{son}_u\))，\(u\) 所在藍鏈長度為偶 / 奇的代價：

• \(\displaystyle dp_{u, v, 0} \leftarrow f_{u, 0}-\max(f_{v, 0}, f_{v, 1}+w(u, v))\)

• \(\displaystyle dp_{u, v, 1} \leftarrow dp_{u, v, 0}+s_{u, 0}\) [\(f_{u, 1}\) 的 \(\max\) 在 \(v\) 處取得]

  \(\displaystyle dp_{u, v, 1} \leftarrow dp_{u, v, 0}+s_{u, 1}\) [\(f_{u, 1}\) 的 \(\max\) 不在 \(v\) 處取得]

再考慮子樹外；令 \(g_{u, 0/1}\) 表示挖去 \(u\) 的子樹 (保留點 \(u\))，\(u\) 所在藍鏈長度為偶 / 奇的答案；轉移為：

• \(\displaystyle g_{v, 0} \leftarrow \max(g_{u, 0}+dp_{u, v, 0}, \max(g_{u, 1}+dp_{u, v, 0}, g_{u, 0}+dp_{u, v, 1})+w(u, v))\)

  其中，\(g_{u, 0}+dp_{u, v, 0}\) 表示將點 \(v\) 單獨空出來

  \(\max(g_{u, 1}+dp_{u, v, 0}, g_{u, 0}+dp_{u, v, 1})+w(u, v)\) 表示欽定 \(u\) 所在藍鏈長為奇，再拼上點 \(v\) 斷成兩條鏈

• \(\displaystyle g_{v, 1} \leftarrow g_{u, 0}+dp_{u, v, 0}+w(u, v)\)，表示將點 \(v\) 拼到子樹外長度為偶的藍鏈上

初始值為 \(g_{1, 0} = 0, g_{1, 1} = -\infty\)；最終答案即為 \(\max (f_{u, 0}+g_{u, 0}, f_{u, 1}+g_{u, 1})\)

時間復雜度 \(O(n)\)

P1453 城市環(huán)路 (基環(huán)樹 DP)

P4381 [IOI 2008] Island (基環(huán)樹 DP)

P2495 [SDOI2011] 消耗戰(zhàn) (虛樹 DP)

7.29

P3233 [HNOI2014] 世界樹 (虛樹 DP)

CF1009F - Dominant Indices (長鏈剖分優(yōu)化 DP)

P5904 [POI 2014] HOT-Hotels 加強版 (神仙樹形 DP + 長鏈剖分優(yōu)化 DP)

P2627 [USACO11OPEN] Mowing the Lawn G (單調隊列優(yōu)化 DP)

P2569 [SCOI2010] 股票交易 (單調隊列優(yōu)化 DP)

7.30

CF939F - Cutlet (設計狀態(tài) + 單調隊列優(yōu)化 DP)

P1912 [NOI2009] 詩人小G (決策單調性優(yōu)化 DP - 二分隊列)

CF868F - Yet Another Minimization Problem (決策單調性優(yōu)化 DP - 分治 + 類莫隊暴力)

P3120 [USACO15FEB] Cow Hopscotch G (類 CDQ 分治優(yōu)化 DP)

P3810 【模板】三維偏序（陌上花開） (CDQ 分治)

7.31

CF449D - Jzzhu and Numbers (SOS DP + 容斥)

P6442 [COCI 2011/2012 #6] KO?ARE (SOS DP + 容斥)

P3287 [SCOI2014] 方伯伯的玉米田 (觀察性質 + 二維樹狀數(shù)組優(yōu)化 DP)

CF53E - Dead Ends (狀壓 DP + 欽定轉移順序)

CF1781F - Bracket Insertion (括號序列轉 \(\pm\) 1 + 分析操作 + 合并同類項優(yōu)化 DP)

8.1

AGC013E - Placing Squares (組合意義 - 平方變放兩個球的方案數(shù) + 矩陣快速冪優(yōu)化 DP)

直接 DP 沒有前途；考慮用組合意義刻畫平方與連乘

有 \(n\) 個格子，你可以在其中插入若干隔板；有 \(m\) 個特殊格 \(x_1, x_2, \cdots, x_m\)，你不能在 \(x_{i}, x_{i}+1\) 格間插入隔板

現(xiàn)在對于每個格子連續(xù)段，你需要選兩個格子 (可重) 放入一個黑球一個白球，求總方案數(shù)

這樣轉化的好處是，每個連續(xù)段中只有 \(2\) 個球，按照這一性質設計狀態(tài)更易于以后進行優(yōu)化

令 \(f_{i, j}\) 表示當前在第 \(i\) 格，當前格到上個隔板間放了 \(j\) 個球的總方案數(shù) ( \(j \in \{0, 1, 2\}\) )

若 \(i-1\) 不為特殊格，則有轉移：

• \(f_{i, 0} = f_{i-1, 0}+f_{i-1, 2}\) (不放隔板 / 放隔板)
• \(f_{i, 1} = 2f_{i-1, 0}+f_{i-1, 1}+2f_{i-1, 2}\) (放黑或白球 / 不放球 / 放隔板+放黑或白球)
• \(f_{i, 2} = f_{i-1, 0}+f_{i-1, 1}+2f_{i-1, 2}\) (放黑白球 / 放另一個球 / 不放隔板或放隔板+放黑白球)

同理，對特殊格，可得轉移：

• \(f_{i, 0} = f_{i-1, 0}\)
• \(f_{i, 1} = 2f_{i-1, 0}+f_{i-1, 1}\)
• \(f_{i, 2} = f_{i-1, 0}+f_{i-1, 1}+f_{i-1, 2}\)

初始值為 \(f_{0, 0} = 1\)，答案即為 \(f_{n, 2}\)

對每個不包含特殊格的連續(xù)段矩陣快速冪優(yōu)化即可；時間復雜度 \(O(m \log n)\)

CF1174E - Ehab and the Expected GCD Problem (觀察性質 + DP)

CF1765C - Card Guessing (拆貢獻 + 概率 DP 轉計數(shù) DP)

由于每次貢獻為 \(1\)，可先將猜對次數(shù)的期望轉化為每次猜對的概率之和

由于每次猜花色是本質不同的決策，此處認為同種花色的牌也是本質不同的牌

設當前考慮第 \(i\) 張牌，令 \(K = \min(k, i-1)\)，顯然我們只關心前 \(K\) 張牌中，出現(xiàn)次數(shù)最少的花色還剩多少張牌

套路地將概率 DP 轉化為計數(shù) DP；不妨設 \(g_{i, j}\) 表示共 \(i\) 張牌，出現(xiàn)次數(shù)最少的花色出現(xiàn) \(j\) 次的方案數(shù) (顯然有多種花色出現(xiàn)次數(shù)最少不影響)

直接轉移似乎不好做，不過注意到花色只有 \(4\) 種，考慮用背包解決

令 \(f_{i, j, k}\) 表示考慮了前 \(i\) 種花色，總共選了 \(j\) 張牌，出現(xiàn)次數(shù)最少的花色出現(xiàn) \(k\) 次的方案數(shù)

顯然有轉移 \(f_{i, j, k} \rightarrow f_{i+1, j+c, \min(k, c)} \cdot \dbinom{j+c}{c} \cdot \dbinom{n}{c} \cdot c!\) (分配插入位置，分配牌，分配順序)

初始值為 \(f_{1, i, i} = \dbinom{n}{i} \cdot i!\)；最終，我們有 \(g_{i, j} = f_{4, i, j}\)

令 \(h_i\) 表示選 \(i\) 張牌的方案數(shù)，顯然有 \(h_i = \sum_{j=0}^{n} g_{i, j}\)

那么對于第 \(i\) 位，貢獻為 \(\displaystyle \frac{\sum_{j=0}^{n} g_{K, j} \cdot (n-j)}{h_{K+1}}\)；特別的，當 \(i=1\) 時，貢獻為 \(\displaystyle \frac{1}{4}\)

注意，這里前 \(K\) 張牌再以前的牌的選擇方案上下抵消了，故不考慮

那么最終答案即為 \(\displaystyle \frac{1}{4} + \sum_{i=2}^{4n} \frac{\sum_{j=0}^{n} g_{K, j} \cdot (n-j)}{h_{K+1}}\)

時間復雜度 \(O(n^3)\)

CF1726E - Almost Perfect (觀察置換環(huán)性質 + 簡單部分 DP 復雜部分枚舉組合)

CF1842G - Tenzing and Random Operations (組合意義 - 連乘變乘法原理 + DP)

8.2

CF1750F - Majority (正難則反 + 前綴和優(yōu)化類連續(xù)段 DP)

8.3

ABC262Ex - Max Limited Sequence (轉化限制 + 線段樹優(yōu)化 DP)

首先，我們可以用數(shù)據(jù)結構求出每個位置的最緊上界 \(u_i\)

顯然，無解當且僅當存在限制 \([l, r, x]\)，使得 \(\max (u_l, u_{l+1}, \cdots, u_r) < x\)

注意到對每個位置，實際上我們只關心該位置是否取到上界

顯然每個上界相互獨立，考慮對每個上界分別計算方案數(shù)后乘起來 (對沒有限制的位置，方案數(shù)為 \(m+1\) )

設當前上界為 \(c\)；取出所有 \(u_i = c\) 的位置 \(i\) 排成一個序列，取出所有 \(X_j = c\) 的限制 \(j\)

注意到對于每個限制 \(j\)，其本質上是要求序列中一段下標區(qū)間內有至少 \(1\) 個位置取到上界

這啟發(fā)我們記錄序列中取到上界的位置；令 \(f_{i, j}\) 表示當前在第 \(i\) 位，上一個取到上界的位置為 \(j\) 的方案數(shù)

先不考慮限制，顯然有轉移：

• \(f_{i, i} \leftarrow f_{i-1, j}\)，表示位置 \(i\) 取到上界
• \(f_{i, j} \leftarrow f_{i-1, j} \times c\)，其中 \(i \ne j\)，表示位置 \(i\) 未取到上界

對于每個限制，我們將其掛在右端點考慮；具體的，對于限制 \([l, r]\)，在 \(i=r\) 時清空所有 \(j < l\) 的 \(f_{i, j}\)

初始值為 \(f_{0, 0} = 1\)，答案為 \(\sum_{j} f_{\text{len}, j}\)

這顯然可以通過支持單點改 + 區(qū)間乘 + 區(qū)間推平 + 全局和的線段樹維護

時間復雜度 \(O(n \log n)\)

AGC030F - Permutation and Minimum (轉化限制 + DP)

先轉化下題意

將 \(1, 2, \cdots, 2n\) 排成一排，從左向右連線匹配，匹配值為左側數(shù)的值，求方案數(shù)

記 \(v_u = 0/1\) 表示 \(u\) 在 \(a_i\) 中不存在 / 存在，對匹配 \((x, y)\) ( \(x < y\) )，分類討論：

• \(v_x = 1, v_y = 1\)，此時匹配位置和值均確定，直接扔掉即可
• \(v_x = 1\) 或 \(v_y = 1\)，此時匹配位置確定
• \(v_x = 0, v_y = 0\)，此時可以自由分配匹配位置

注意到不好用 DP 刻畫 "自由分配匹配位置"，不過你發(fā)現(xiàn)第三類匹配的個數(shù)確定，考慮先轉化為無序，最后乘階乘定序

因此，兩種匹配方案不同，當且僅當：

• 匹配值不同，即存在位置 \(i\) 在第一種方案中是左端點，第二種方案中不是
• 匹配位置不同，即存在匹配 \((i, x), (i, y)\) 使得 \(x \ne y\) 且 \(v_x = 1, v_y = 1\)

考慮從大向小 DP，逐個確定匹配位置，記 \(f_{i, j, k}\) 表示從 \(2n\) 填到 \(i\)，有 \(j\) 個 \(v_x = 0\) 的右端點，有 \(k\) 個 \(v_x = 1\) 的右端點

易得轉移：

• \(v_i = 0\) 時：
  • \(f_{i, j, k} \leftarrow f_{i+1, j+1, k}\)，表示匹配一個 \(v_x = 0\) 的右端點
  • \(f_{i, j, k} \leftarrow f_{i+1, j, k+1} \times (k+1)\)，表示匹配一個 \(v_x = 1\) 的右端點，需要考慮匹配位置
  • \(f_{i, j, k} \leftarrow f_{i+1, j-1, k}\)，表示不匹配
• \(v_i = 1\) 時：
  • \(f_{i, j, k} \leftarrow f_{i+1, j+1, k} \times (j+1)\)，表示匹配一個 \(v_x = 0\) 的右端點
  • \(f_{i, j, k} \leftarrow f_{i+1, j, k-1}\)，表示不匹配

初始值為 \(f_{2n+1, 0, 0} = 1\)，答案為 \(f_{1, 0, 0}\)

時間復雜度 \(O(n^3)\)

8.4

ARC106E - Medals (Hall 定理 + SOS DP)

CF21D - Traveling Graph (歐拉回路狀壓 DP)

8.5

CF1773G - Game of Questions (觀察性質 - 去除無用狀態(tài) + 狀壓 DP)

注意到 \(m \le 17\)，考慮對人狀壓一下

不妨令 \(f_S\) 表示場上剩余的人組成的集合為 \(S\) 時，Genie 的獲勝概率

若轉移時直接枚舉問題，有可能會選重，記在狀態(tài)里又接受不了；但注意到，重復選擇問題不會使 \(S\) 變化，因此無需考慮這件事

具體的，設有 \(c_0\) 種問題可以使 \(S\) 減少，\(c_1\) 種問題可以使 \(S\) 變成 \(T\) ( $ T \varsubsetneqq S$ )，即有 \(\displaystyle f_S \leftarrow f_T \times \frac{c_1}{c_0}\) (只在 \(S\) 產生變化時統(tǒng)計)

直接 \(O(n2^m)\) 枚舉問題顯然無法接受，考慮預處理 \(g_{S, T}\) ( \(T \subset S\) ) 表示使 \(S\) 變成 \(T\) 的問題數(shù)量

對 \(g_{S, T}\) 的轉移，考慮欽定一個 \(x (x \notin S)\)，則所有使 \(S\) 變成 \(T\) 的問題可分為同時 ban 掉 \(x\) 與不同時 ban 掉 \(x\) 兩類

顯然有轉移 \(g_{S, T} \leftarrow g_{S \cup \{x\}, T} + g_{S \cup \{x\}, T \cup \{x\}}\)

對 \(f_S\)，則有轉移 \(\displaystyle f_S \leftarrow \frac{\sum_{T \varsubsetneqq S} f_{T} g_{S, T}}{n-g_{S, \varnothing}-g_{S, S}}\)

初始值為對所有 \(g_{S, \varnothing}+g_{S, S} = n\) 的 \(S\)，\(f_{S}= [1 \in S]\)；答案即為 \(f_{\{1, 2, \cdots, m\}}\)

時間復雜度為 \(O(nm + 3^m)\)

P9129 - [USACO23FEB] Piling Papers G (區(qū)間 DP 套類數(shù)位 DP)

8.6 - 8.9

準備講課 PPT + 補 whk

8.10 - 8.16

軍訓

8.17

ARC103F - Distance Sums (觀察性質 + 類拓撲思想)

CF1528C - Trees of Tranquillity (虛樹思想貪心)

CF842E - Nikita and game (樹的直徑性質 - 交于一點或一邊 + 維護左右集合)

CF2108E - Spruce Dispute (拆貢獻 + 貪心 - 最大子樹最小取重心)

CF1783G - Weighed Tree Radius (補齊對稱性 + 觀察性質 + 線段樹維護區(qū)間直徑)

AGC018D - Tree and Hamilton Path (拆貢獻 + 貪心 - 最大子樹最小取重心 + 回路減邊變路徑)

8.18

8.18 T1 - Rainbow 的信號 (拆位 + 拆貢獻)

8.18 T2 - Freda 的傳呼機 (仙人掌最短路)

8.18 T4 - Tree (分數(shù)規(guī)劃 + 樹形 DP)

8.19

8.18 T3 - Circle (觀察性質 + 類數(shù)位 DP)

P12205 [COI 2022] 通行證件 / Vinjete (線段樹維護區(qū)間 > 0 個數(shù))

8.20

P6348 [PA 2011] Journeys (線段樹優(yōu)化建圖)

ABC414G - AtCoder Express 4 (線段樹優(yōu)化建圖 - 左右端點差分)

P6453 [COCI 2008/2009 #4] PERIODNI (笛卡爾樹上 DP)

P3809 【模板】后綴排序 ( \(O(n \log n)\) SA)

令 \(\text{sa}_i\) 表示排名為 \(i\) 的后綴位置，\(\text{rk}_i\) 為后綴 \(\text{suf}_i\) 的排名

做法 1：\(O(n \log^2 n)\)

考慮直接對每個后綴排序，這樣是 \(O(n^2 \log n)\) 的

考慮優(yōu)化比較；二分哈希求 \(\text{lcp}\) 后比較下一位即可，這樣單次比較 \(O(\log n)\)，總時間復雜度 \(O(n \log^2 n)\)

做法 2：\(O(n \log^2 n)\)

考慮倍增的思想求解

令 \(\text{rk}_{i}^{j}\) 表示考慮所有長為 \(2^j\) 的子串 (不足補極小值)，從 \(i\) 開始的排名，\(\text{sa}_{i}^{j}\) 類似

初始時，我們對每個字符排序可得 \(\text{rk}_{i}^{1}\) 與 \(\text{sa}_{i}^{1}\)

從 \(j\) 倍增到 \(j+1\) 時，對所有位置 \(i\) 以 \(\text{rk}_{i}^{j}\) 以第 \(1\) 關鍵字、\(\text{rk}_{i+2^j}^{j}\) 以第 \(2\) 關鍵字排序即可

注意，需要特別處理 \(\text{rk}_{p}^{j} = \text{rk}_{q}^{j}\) 且 \(\text{rk}_{p+2^j}^{j} = \text{rk}_{q+2^j}^{j}\) 的情況，此時 \(\text{rk}_{p}^{j+1} = \text{rk}_{q}^{j+1}\)；排好序后重新掃一遍即可

只需做到 \(2^j \ge n\)，共 \(O(\log n)\) 輪，總時間復雜度 \(O(n \log^2 n)\)，瓶頸在排序

做法 3：\(O(n \log n)\)

做法 2 的瓶頸在排序，用基數(shù)排序 (做兩次計數(shù)排序) 優(yōu)化即可

實現(xiàn)上的小細節(jié)：

• 第 \(1\) 次排序無需考慮第 \(2\) 關鍵字

• 對第 \(2\) 關鍵字排序無需計數(shù)排序：

  for (int i=n-w+1; i<=n; i++) tot++, id[tot] = i (處理 \(i+w > n\) 的情況，此時沒有先后順序)

  for (int i=1; i<=n; i++) if (sa[i] > w) tot++, id[tot] = sa[i]-w (直接處理 \(i+w\) 的順序)

• 排好序后需要重新掃一遍處理 \(\text{rk}\) 相同的情況

• 可動態(tài)令基數(shù)排序的值域 \(V = \max\{\text{rk}_i\}\)

• \(\max\{\text{rk}_i\} \ge n\) 時無需繼續(xù)排序，直接 break 即可

令 \(\text{h}_i = \text{lcp}(\text{suf}_{\text{sa}_{i-1}}, \text{suf}_{\text{sa}_{i}})\)，考慮如何求 \(\text{h}_i\)

結論 1：\(\text{h}_{\text{rk}_i} \ge \text{h}_{\text{rk}_{i-1}}-1\)

當 \(\text{h}_{\text{rk}_{i-1}} \le 1\) 時，顯然成立

當 \(\text{h}_{\text{rk}_{i-1}} > 1\) 時，令舊 \(\text{lcp}\) 為 \(\text{aA}\)，其中 \(\text{a}\) 為字符，\(\text{A}\) 為串；因此，令 \(\text{suf}_{i-1}\) 為 \(\text{aAD}\)，另一個為 \(\text{aAB}\)

因此，我們有 \(\text{suf}_i\) 為 \(\text{AD}\)，且存在 \(\text{AB}\)；由于 \(\text{rk}_i-1\) 比 \(\text{rk}_i\) 僅小 \(1\)，因此有 \(AB \le \text{suf}_{\text{sa}_{\text{rk}_i-1}} < AD\)

綜上，新 \(\text{lcp}\) 至少為 \(\text{A}\)，證畢

我們可以根據(jù)這一性質暴力求 \(\text{h}_i\) (初始值 \(\text{h}_1 = 0\) )

結論 2：\(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_j) = \min_{\text{rk}_i+1 \le k \le \text{rk}_j} \text{h}_k\)

顯然，必有 \(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_j) \ge \min_{\text{rk}_i+1 \le k \le \text{rk}_j} \text{h}_k\)

感性理解上，由于我們按字典序枚舉，\(\text{lcp}\) 只要掉下去就回不來了，成立

8.21

AT_ddcc2020_final_c - Smaller-Suffix-Free Sequences (SA)

題意：給定串 \(s\)，對其每個后綴，求出該后綴的一個最長前綴，滿足這個前綴為 Lyndon 串

一個串稱為 Lyndon 串，當且僅當其字典序嚴格小于其所有后綴；\(1 \le |s| \le 2 \times 10^5\)

令原串為 \(s\)，\(s\) 的一個后綴的前綴為 \(t\)，\(t\) 的一個后綴為 \(t'\)

容易發(fā)現(xiàn)，\(t < t'\) 與 \(t+x < t'+x\) 是等價的；那么我們只需判斷原串后綴與后綴的字典序關系即可

這啟示我們建出 SA；則原題可轉化為：

• 對每個 \(1 \le i \le n\)，求出最大的 \(j\) 使得 \(\displaystyle \text{rk}_i = \min_{i \le p \le j} \text{rk}_p\)

單調棧維護即可；時間復雜度 \(O(n \log n)\)，瓶頸在建 SA

P2178 [NOI2015] 品酒大會 (SA - 并查集維護 \(h_i\) )

由于有經典結論 \(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_j) = \min_{\text{rk}_i+1 \le k \le \text{rk}_j} \text{h}_k\)，考慮建出 SA

考慮從大到小加入 \(\text{h}_{\text{rk}_i}\)，每個 \(\text{h}_{\text{rk}_i}\) 放在 \(\text{rk}_i\) 位置上，過程中會形成許多連續(xù)段；考慮用并查集維護

具體的，對于連續(xù)段 \([l, r]\)，其對應滿足 \(l-1 \le \text{rk}_i \le r-1\) 且 \(l \le \text{rk}_j \le r\) ( \(i < j\) ) 的 \(\text{lcp}(\text{suf}_i, \text{suf}_j)\)

對第一問，連續(xù)段 \([l, r]\) 對應的選擇方案數(shù)為：

• \(l = 1\)，則為 \(\displaystyle 1+2+\cdots+(r-1) = \frac{1}{2} r(r-1)\)
• \(l \ne 1\)，則為 \(\displaystyle 1+2+\cdots+(r-l+1) = \frac{1}{2} (r-l+2)(r-l+1)\)

這啟示我們維護連續(xù)段的左右端點，合并時減去兩個小區(qū)間貢獻再加上新區(qū)間貢獻即可

對第二問，合并 \([l_1, r_1], [l_2, r_2]\) 時 (不妨設 \(l_2 > r_1\) )：

• 左端點取在 \([\max(1, l_1-1), r_1-1]\)，右端點取在 \([l_1, r_1]\)，已經在計算 \([l_1, r_1]\) 的答案時貢獻過

• 左端點取在 \([\max(1, l_2-1), r_2-1]\)，右端點取在 \([l_2, r_2]\)，已經在計算 \([l_2, r_2]\) 的答案時貢獻過

• 左端點取在 \([\max(1, l_1-1), r_1-1]\)，右端點取在 \([l_2, r_2]\)

  這啟示我們對區(qū)間 \([l, r]\) 維護 \(a\) 上 \([\text{sa}_l, \text{sa}_{r-1}]\) 的最大 / 次大 / 最小 / 次小值

  合并時，我們：

  • 用 ( \([l_1, r_1]\) 的相關值 + \(a_{\text{sa}_{l_1-1}} [l_1 \ne 1]\) ) 與 ( \([l_2, r_2]\) 的相關值 + \(a_{\text{sa}_{r_2}}\) ) 更新 \([l_1, r_2]\) 答案
  • 用 ( \([l_1, r_1]\) 的相關值 + \(a_{\text{sa}_{r_1}}\) ) 與 ( \([l_2, r_2]\) 的相關值 ) 更新 \([l_1, r_2]\) 相關值
  • 根據(jù)實現(xiàn)不同，當 \(l_1 = r_1\) 時可能需要特殊處理 (如補上 \(a_{\text{sa}_{l_1}}\) )

時間復雜度 \(O(n \log n)\)，瓶頸在建 SA

8.22

P9664 [ICPC 2021 Macao R] LCS Spanning Tree (SA - 只需考慮 sa 相鄰的 lcs)

首先考慮只有兩個串 \(s_i, s_j\) 怎么做

\(\text{lcs}\) 自然啟發(fā)我們建 SA，這啟示我們將 \(s_i, s_j\) 拼接起來，在 \(s_i\) 中選取左端點 \(l\)，在 \(s_j\) 中選取右端點 \(r\) 求 \(\text{lcp}\)

此時出現(xiàn)了兩個問題：

1. \(\text{lcp}(\text{suf}_l, \text{suf}_r) \ge |s_i|-l+1\)，即 \(\text{lcp}\) 超出 \(s_i\)

   這可以通過在 \(s_i, s_j\) 間添加特殊連接符規(guī)避

2. 暴力選取 \(l, r\) 在時間復雜度上無法接受

   注意到只有排名相鄰的后綴是有用的，枚舉排名 \(i\)，貢獻為 \(\text{lcp}(\text{suf}_{\text{sa}_{i-1}}, \text{suf}_{\text{sa}_i}) = \text{h}_i\)

   綜上，判掉 \(\text{sa}_{i-1}\) 與 \(sa_i\) 在一個串中的情況，連邊 \((\text{sa}_{i-1}, \text{sa}_i, \text{h}_i)\) 即可

多個串沒有本質區(qū)別，全部拼起來，中間加上不同的連接符即可

時間復雜度 \(O(n \log n)\)

CF547E - Mike and Friends (SA + 二維數(shù)點)

省流：我覺得我真想不清楚細節(jié)，所以寫的會繁瑣億點

類比上題，套路地將 \(s_1, s_2, \cdots, s_n\) 拼成新串，中間加上不同的分割符；記新串中 \(s_i\) 的對應位置為 \([\text{st}_i, \text{ed}_i]\)

對于查詢 \((l, r, k)\)，對滿足條件的新串位置 \(i\)，考慮分討限制條件：

• 顯然要求 \(i \in [\text{st}_l, \text{ed}_r]\)
• 令 \(p = \text{st}_k\)，若 \(\text{rk}_i < \text{rk}_{p}\)，則有 \(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_p) = \min_{\text{rk}_i+1 \le q \le \text{rk}_p} \text{h}_q = |s_k|\)
• 若 \(\text{rk}_i = \text{rk}_{p}\)，事實上即 \(i = p\)，顯然成立
• 若 \(\text{rk}_i > \text{rk}_{p}\)，則有 \(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_p) = \min_{\text{rk}_p+1 \le q \le \text{rk}_i} \text{h}_q = |s_k|\)

這啟示我們對每個位置 \(i\) 維護：

• 最靠前的 \(l_i\)，滿足 \(\displaystyle \min_{l \le j \le \text{rk}_i} \text{h}_{j} = \text{h}_{\text{rk}_i}\)
• 最靠后的 \(r_i\)，滿足 \(\displaystyle \min_{\text{rk}_{i+1} \le j \le r} \text{h}_{j} = \text{h}_{\text{rk}_{i+1}}\)

這里直接二分維護即可

回到詢問 \((l, r, k)\)，對滿足條件的新串位置 \(i\)，考慮轉化限制條件：

• \(i \in [\text{st}_l, \text{ed}_r]\)
• \(\text{rk}_i\) 也需在一個區(qū)間 \([l', r']\) 內，令 \(p = \text{st}_k\)，具體的：
  • 若 \(\text{h}_{\text{rk}_p} = |s_k|\)，則左半?yún)^(qū)間成立，有 \(l' = l_k\)；反之 \(l' = \text{rk}_p\)
  • 若 \(\text{h}_{\text{rk}_{p+1}} = |s_k|\)，則右半?yún)^(qū)間成立，有 \(r' = r_k\)；反之 \(r' = \text{rk}_p\)

那么直接二維數(shù)點即可；時間復雜度 \(O(n \log n)\)

8.23

CF1923F - Shrink-Reverse (觀察性質 + SA)

首先考慮沒有翻轉操作怎么做

我們每次必然貪心地將最靠前的 \(1\) 與最靠后的 \(0\) 交換；雙指針維護即可，這部分時間復雜度 \(O(n)\)

考慮觀察翻轉操作的性質

顯然，\(1\) 次翻轉可以去前導零，\(2\) 次可以去后導零，\(\ge 3\) 次是沒有意義的

對于 \(2\) 次翻轉，我們發(fā)現(xiàn)去后導零并沒有改變答案；若翻轉后再交換，顯然可以不劣地等效為先交換再翻轉

綜上，只需考慮 \(1\) 次翻轉的情況，且這次翻轉必然最后進行

類比沒有翻轉的情況，一個 naive 的想法是將最靠后的 \(1\) 與前導零的末尾交換

如 \(00101100\) 的情況就可以 hack 掉這個做法，因為我們可以與中間的 \(0\) 交換以縮小長度

這啟示我們先確定最小長度 \(L\)；顯然先翻轉 \(s\) 不影響答案，以下的 \(s\) 均指翻轉后的串

對每個 \(i\)，考慮求出最靠前的 \(r_i\) 使得可以將所有 \(1\) 換到 \([i, r_i]\) 中：

• 記 \([i, r_i]\) 中 \(0\) 的個數(shù)為 \(c_0\)，\([i, r_i]\) 外 \(1\) 的個數(shù)為 \(c_1\)

  則 \([i, r_i]\) 合法等價于 \(c_1 \le k-1\) (能換進來) 且 \(c_1 \le c_0\) (有地方容納)

\(i\) 增大時，\(c_0\) 不增，\(c_1\) 不降，\(r_i\) 也是單調的；于是這部分也可以雙指針做到 \(O(n)\)

接下來考慮最小化字典序；顯然換進來的 \(1\) 會優(yōu)先向后放，比的實際上是后綴的一段前綴的字典序

這啟示我們跑 SA，按 \(\text{rk}\) 從小到大枚舉，第一個合法的長度為 \(L\) 的前綴就是答案；證明：

• 若 \(\text{lcp} > L\)，由于外面的 \(1\) 全部被換進來，已經完全相同，前后順序沒有影響

• 若 \(\text{lcp} \le L\) 且換進來的 \(1\) 沒有影響 \(\text{lcp}\)，直接按 \(\text{rk}\) 排就是對的

  若 \(\text{lcp} \le L\) 且換進來的 \(1\) 影響了 \(\text{lcp}\)，由于里面 \(1\) 的總數(shù)確定，一定是將一段后綴部填成 \(1\)，前后順序沒有影響

時間復雜度 \(O(n \log n)\)，瓶頸在建 SA

8.24

P4094 [HEOI2016/TJOI2016] 字符串 (SA + 二分答案 + 主席樹 - 區(qū)間查非嚴格前驅 / 后綴)

子串 \(\text{lcp}\) 自然啟示我們建 SA，同時把子串拼成后綴考慮

對于查詢 \((a, b, c, d)\)，其答案為：

• \(\displaystyle \max_{a \le p \le b} \{\min\{\text{lcp}(\text{suf}_p, \text{suf}_c),\ b-p+1,\ d-c+1\}\}\)

  這個式子表示對后綴求 \(\text{lcp}\) 后限制不能超出子串長度

限制不能超出 \([a, b]\) 子串長度的 \(b-p+1\) 一項很煩，考慮怎么去掉

考慮二分答案 \(\text{mid}\) 再刻畫限制，提前確定合法區(qū)間 \([a, b-\text{mid}+1]\)，這樣就無需考慮這個問題

套路地，對于 \(a \le i \le b-\text{mid}+1\)，我們對 \(\text{lcp}(\text{suf}_i, \text{suf}_c)\) 分類討論：

• \(\text{rk}_i \le \text{rk}_c-1\)，此時 \(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_c) = \min_{\text{rk}_i+1 \le p \le \text{rk}_c} \text{h}_p\)，只需取 \(\le \text{rk}_c-1\) 的最大的 \(\text{rk}_i\) 計算
• \(\text{rk}_c+1 \le \text{rk}_i\)，此時 \(\displaystyle \text{lcp}(\text{suf}_i, \text{suf}_c) = \min_{\text{rk}_c+1 \le p \le \text{rk}_i} \text{h}_p\)，只需取 \(\ge \text{rk}_c+1\) 的最小的 \(\text{rk}_i\) 計算
• \(\text{rk}_i = \text{rk}_c\)，此時 \(i = c\)，答案即為 \(\min\{b-i+1, d-i+1\}\)

綜上，我們需要支持區(qū)間查非嚴格前驅 / 后繼

一個直觀的想法是二分排名 + 靜態(tài)區(qū)間第 \(k\) 小，上主席樹，總時間復雜度 \(O(n \log^3 n)\)

事實上，可以發(fā)現(xiàn)二分排名是不必要的，設查詢區(qū)間為 \([l, r]\)：

• 若對 \(x\) 求前驅，線段樹上二分查出 \(x\) 的排名，再對排名求值即可
• 若對 \(x\) 求后繼，線段樹上二分查出 \(x-1\) 的排名，再對排名 \(+1\) 求值即可

綜上，我們維護 SA + 主席樹 + 對 \(\text{h}_i\) 的 ST 表，總時間復雜度 \(O(n \log^2 n)\)

8.25

P4248 [AHOI2013] 差異

將式子拆成兩部分，即 \(\displaystyle \sum_{1 \le i < j \le n} (|\text{suf}_i|+|\text{suf}_j|)\) 與 \(\displaystyle \sum_{1 \le i < j \le n} \text{lcp}(\text{suf}_i, \text{suf}_j)\)

前半部分易知為 \(\displaystyle \sum_{i=1}^{n-1} (\frac{i(i+1)}{2}+(n-i+1)(n-i))\)，考慮如何求后半部分

\(i = j\) 的情況本身不合法無需統(tǒng)計，易得 \(\text{h}_i\) 上的每個區(qū)間 \([l, r]\) 都會貢獻 \(\displaystyle \min_{l \le p \le r} \text{h}_p\)

對每個 \(i\)，處理出：

• 最靠前的 \(\text{ls}_i\) 使得 \(\displaystyle \min_{\text{ls}_i \le p \le i}\text{h}_p = \text{h}_i\) 且在 \(\text{h}_i\) 處唯一取到
• 最靠后的 \(\text{rs}_i\) 使得 \(\displaystyle \min_{i \le p \le \text{rs}_i} \text{h}_p = \text{h}_i\)

在 \([\text{ls}_i, i]\) 中選左端點，\([i, \text{rs}_i]\) 中選右端點，貢獻即為 \((i-\text{ls}_i+1) \times (\text{rs}_i-i+1) \times \text{h}_i\)

可二分 + ST 表或單調棧維護 \(\text{ls}_i\) 與 \(\text{rs}_i\)，時間復雜度 \(O(n \log n)\)

8.26

P5161 WD與數(shù)列

對位差相等是困難的；注意到兩序列增量相同，考慮對原序列差分

問題轉化為：計數(shù)存在多少對 \([l_1, r_1], [l_2, r_2]\)，使得 \(r_1 < l_2\) 且 \(a_{[l_1+1, r_1]} = a_{[l_2+1, r_2]}\) (注意第 \(1\) 位可以不同)

那么貢獻分為兩部分：

• 只有第 \(1\) 位，貢獻為 \(\binom{n}{2}\)

• 扔掉第 \(1\) 位，計數(shù)存在多少對不交且不相鄰的相等子串

  注意，雖然此處視為 "扔掉"，最后還是要往前拼 \(1\) 位的，子串左端點不能為 \(1\)

考慮處理不交且不相鄰的相等子串對數(shù)

令靠前的子串開頭為 \(i\)，靠后的為 \(j\)，考慮將 "不相鄰" 刻畫為對 \(j-i-1\) 取 \(\min\)

答案式子為 \(\displaystyle \sum_{1 < i < j \le n} \min\{\text{lcp}(\text{suf}_i, \text{suf}_j), j-i-1\}\)

考慮先求出 \(\displaystyle \sum_{1 < i < j \le n} \text{lcp}(\text{suf}_i, \text{suf}_j)\)，再把 \(\ge j-i\) 的部分換成 \(j-i-1\)

前半部分是容易的，可以參考上道題

對于后半部分，考慮枚舉 \(\text{len} = j-i\)，使用 P1117 [NOI2016] 優(yōu)秀的拆分 的 trick：

• 在 \(\text{len}, 2 \times \text{len}, 3 \times \text{len}, \cdots\) 處設關鍵點

• 對關鍵點 \(k\) 與 \(k+\text{len}\)，求出 \(i \in [\max\{2, k-len+1\}, k]\) 的貢獻

  注意到這樣處理不到 \(i\) 在倒數(shù)第二個關鍵點后的情況，不過此時必有 \(\text{lcp} < \text{len}\)，沒有貢獻

• 求出 \(\text{lcp}(\text{suf}_k, \text{suf}_{k+\text{len}})\) 與 \(\text{lcs}(\text{pre}_k, \text{pre}_{k+\text{len}})\)，則只需考慮 \(i \in [\max\{2, k-\min\{\text{len}, \text{lcs}\}+1\}, k]\)

  此時 \(\text{lcp}\) 長度的貢獻為等差數(shù)列，可以 \(O(1)\) 求出

使用 SA 維護原串與反串的后綴 \(\text{lcp}\) 即可

時間復雜度 \(O(n \log n)\)

8.27

P3804 【模板】后綴自動機（SAM）

SAM (后綴自動機)，可以始終在 \(O(|s|)\) 的結點和邊的代價下存儲 \(s\) 的子串信息，將 \(s\) 的子串高度壓縮以存儲

下面給出一些定義：

• \(\text{endpos}\)：對 \(s\) 及其子串 \(t\)，定義 \(t\) 的 \(\text{endpos}\) 集合為 \(s\) 中所有 \(t\) 出現(xiàn)的結束位置構成的集合

  例：對 aabab，子串 ab 的 \(\text{endpos}\) 集合為 \(\{3, 5\}\)

  引理 1：對 \(s\) 及其子串 \(u, v (|v| \le |u|)\)，\(u\) 與 \(v\) 的 \(\text{endpos}\) 集合相同 \(\iff v\) 在 \(s\) 中每次出現(xiàn)都是以 \(u\) 的后綴的形式

• \(\text{endpos}\) 等價類：\(\text{endpos}\) 相同的所有子串構成的集合

  例：對 aabab，子串 ab 與 b 同屬一個 \(\text{endpos}\) 等價類

  引理 2：\(\text{endpos}\) 等價類中子串的長度連續(xù)，且所有子串均為最長子串的后綴

SAM 中的每個節(jié)點實際上代表一個 \(\text{endpos}\) 等價類

從初始節(jié)點 \(\text{rt}\) 到節(jié)點 \(u\) 會經過許多轉移邊，將轉移邊上的字符寫下來形成字符串，這些字符串的 \(\text{endpos}\) 集合都相同

在 SAM 上的每個節(jié)點 \(u\)，我們維護：

• \(\text{len}\)：當前 \(\text{endpos}\) 等價類中最長子串的長度

• \(\delta(u, c)\)：\(u\) 經過轉移邊 \(c\) 到達的節(jié)點

• \(\text{link}\) (后綴鏈接)：設當前 \(\text{endpos}\) 等價類中最長子串為 \(p\)，最長的不屬于當前 \(\text{endpos}\) 集合的 \(p\) 的后綴為 \(q\)

  則 \(u\) 的后綴鏈接 \(\text{link}(u)\) 指向代表 \(q\) 所在 \(\text{endpos}\) 等價類的節(jié)點

  引理 3：將所有 \(u\) 與 \(\text{link}(u)\) 連邊，會形成一個樹形結構

  證明：顯然只會從長串向短串連邊，最終都連到初始節(jié)點 \(\text{rt}\)，必然形成以 \(\text{rt}\) 為根的樹

  我們也將這一樹形結構稱為 \(\text{parent tree}\)

初始時，創(chuàng)建初始節(jié)點 \(\text{rt}\)，代表空串；令 \(\text{len}(\text{rt}) = 0\) 且 \(\text{link}(\text{rt}) = -1\)

考慮增量構造 SAM，設原串為 \(s\)，每次加入一個字符 \(c\) 變?yōu)?\(s+c\)，創(chuàng)建新節(jié)點 \(u\) 代表當前插入狀態(tài)

設 \(s+c\) 的末尾位置為 \(i\)，則 \(u\) 實際代表的 \(\text{endpos}\) 集合為 \(\{i\}\)

設上次插入狀態(tài)的對應節(jié)點為 \(v\)，考慮維護 \(u\) 的 \(\text{len, link}\) 及其他節(jié)點向 \(u\) 的轉移關系：

• 顯然有 \(\text{len}(u) = \text{len}(v)+1\)

• 考慮嘗試在 \(s\) 的每個后綴 \(\text{endpos}\) 等價類的末尾追加 \(c\) 形成 \(s+c\) 的后綴 \(\text{endpos}\) 等價類

  我們從 \(v\) 開始跳 \(\text{link}\)，設當前跳到的節(jié)點為 \(p\)，對應 \(\text{endpos}\) 等價類中的最長子串為 \(t\)：

  • 若 \(\delta(p, c)\) 不存在，說明子串 \(t+c\) 在 \(s\) 中不存在，在 \(s+c\) 中的 \(\text{endpos}\) 集合就是 \(\{i\}\)

    易知 \(t+c\) 與 \(s+c\) 同屬一個 \(\text{endpos}\) 等價類，因此，令 \(\delta(p, c) = u\)

  考慮一直跳 \(\text{link}\) 直到跳到 \(-1\) 或出現(xiàn)第一個滿足 \(\delta(p, c)\) 存在的節(jié)點 \(p\)：

  • 若跳到 \(-1\)，說明 \(c\) 這個字符在 \(s\) 中不存在，直接令 \(\text{link}(u) = \text{rt}\) 即可

  • 若出現(xiàn)第一個滿足 \(\delta(p, c)\) 存在的節(jié)點 \(p\)，令 \(q = \delta(p, c)\)

    • 若 \(\text{len}(q) = \text{len}(p)+1\)，則 \(t+c\) 剛好為最長的 \(\text{endpos}\) 等價類不為 \(\{i\}\) 的后綴，令 \(\text{link}(u) = q\) 即可

    • 需要注意，此時 \(q\) 代表的 \(\text{endpos}\) 等價類中的最長子串不一定為 \(p+c\)，可能更長

      例：對字符串 abb，插入最后一個 b 前 SAM 結構如下：

      • 節(jié)點 \(0\)，\(\text{endpos}\) 等價類中為空串，\(\text{link} = -1\)
      • 節(jié)點 \(1\)，\(\text{endpos}\) 等價類中為 {a}，\(\text{link} = 0\)，連邊 \(\delta(0, a) = 1\)
      • 節(jié)點 \(2\)，\(\text{endpos}\) 等價類中為 {ab, b}，\(\text{link} = 0\)，連邊 \(\delta(0, b) = 2, \delta(1, b) = 2\)

      插入最后一個 b 時，我們會跳 \(\text{link}\) 到 \(0\)，此時 \(p = 0, q = \delta(0, b) = 2\)

      此時節(jié)點 \(2\) 代表的 \(\text{endpos}\) 等價類中除了 b，還有更長的 ab

      以此例為例，我們發(fā)現(xiàn)節(jié)點 \(3\) (即新創(chuàng)建的 \(u\) ) 代表的 \(\text{endpos}\) 等價類應為 {abb, bb}

      此時節(jié)點 \(3\) 的 \(\text{link}\) 對應的 \(\text{endpos}\) 等價類應為 b；這啟示我們將節(jié)點 \(2\) 進行 "分裂"，變?yōu)?ab 與 b

    • 綜上，若 \(\text{len}(q) > \text{len}(p)+1\)，考慮將節(jié)點 \(q\) 分裂出一個 \(q'\)，后綴長度分界線即為 \(\text{len}(p)+1\)

      令 \(q\) 代表的 \(\text{endpos}\) 集合為 \(S\)，可視為新節(jié)點 \(q\) 仍維護 \(\text{endpos}\) 集合 \(S\)，新節(jié)點 \(q'\) 維護 \(S \cup \{i\}\)

      具體的，先克隆 \(q' = q\) (即儲存信息全部相同)，令：

      • \(\text{len}(q') = \text{len}(p)+1\)
      • \(\text{link}(u) = q'\)
      • \(\text{link}(q) = q'\)

      接下來從節(jié)點 \(p\) 繼續(xù)跳 \(\text{link}\)，將所有 \(\delta(p', c) = q\) 改為 \(\delta(p', c) = q'\) 即可

現(xiàn)在我們已經能夠建出 SAM，回到本題

考慮暴力枚舉每個節(jié)點 \(i\)，將 \(\text{link}(i)\) 與 \(i\) 連邊，建出 \(\text{parent tree}\)

記錄每次插入時的節(jié)點 \(u\)，將這些點賦權 \(1\)，其他點賦權 \(0\) (實現(xiàn)時最好不要直接在 SAM 節(jié)點上記錄權，復制時容易出錯)

易知對于節(jié)點 \(i\)，其代表的 \(\text{endpos}\) 集合的大小即為 \(i\) 子樹內 \(1\) 的個數(shù)

對于一個 \(\text{endpos}\) 等價類，我們肯定取最長的子串，長度即為 \(\text{len}(i)\)；那么 dfs 一遍取 \(\max\) 即可

若直接開數(shù)組存 \(\delta(u, c)\)，時間復雜度 \(O(n)\)，空間復雜度 \(O(n|\Sigma|)\)

若使用 \(\text{map}\) 存 \(\delta(u, c)\)，時間復雜度 \(O(n \log |\Sigma|)\)，空間復雜度 \(O(n)\)

SP1812 LCS2 - Longest Common Substring II (SAM - 兩串求最長公共子串 (lcs))

看到求 \(\text{lcs}\)，考慮建 SAM

先考慮兩個串 \(s, t\) 怎么做

對 \(s\) 建 SAM，遍歷 \(t\) 放到 SAM 中查詢

設當前遍歷到 \(t_i\)；考慮維護 \(t_{[1, i]}\) 在 SAM 上的匹配位置 \(u\) 以及匹配長度 \(l\)，設 \(t_{[1, i-1]}\) 的相關信息為 \(u'\) 與 \(l'\)：

• 若 \(\delta(u', t_i)\) 存在，則令 \(u = \delta(u', t_i)\)，\(l = l'+1\)
• 若 \(\delta(u', t_i)\) 不存在，考慮類似建 SAM 時插入字符的思想，跳 \(\text{link}\) 直到 \(\delta(u', t_i)\) 存在：

  • 若跳完 \(\text{link}\) 也沒有找到使 \(\delta(u', t_i)\) 存在的 \(u'\)，令 \(u = \text{rt}\)，\(l = 0\)

  • 反之，令 \(u = \delta(u', t_i)\)，\(l = \text{len}(u')+1\)

    對任意節(jié)點 \(i\)，都有 \(i\) 代表的 \(\text{endpos}\) 等價類中最短子串長度 \(>\) \(\text{len}(\text{link}(i))\)

    因此，跳 \(\text{link}\) 時 \(\text{len}(u')+1\) 必然是能取到的

那么我們在每個點記錄最長匹配長度即可

對多個串，考慮對最短串建 SAM，枚舉每個串做兩個串的匹配

我們在 SAM 上每個節(jié)點記錄當前輪最長匹配長度 \(w_i\)，歷史匹配最小值 \(\text{mn}_i\)

每輪匹配結束后，令 \(\text{mn}_i \leftarrow \min\{\text{mn}_i, w_i\}\)；最終 \(\max\{\text{mn}_i\}\) 即為答案

注意，若 SAM 上的節(jié)點 \(i\) 匹配，\(\text{parent tree}\) 上 \(i\) 的每個祖先也都能匹配：

• 在兩個串匹配時，選祖先匹配肯定不如選自己匹配優(yōu)，因此可以不管

• 在多個串匹配時，由于需要對歷史匹配最小值取 \(\min\)，選自己不一定優(yōu)

  因此，我們記錄每個點當前輪的最長匹配長度 \(w_i\)，在匹配結束后遍歷 \(\text{parent tree}\) 更新即可

  具體的，設 \(v \in \text{son}(u)\)，若 \(w_v > 0\)，則令 \(w_u \leftarrow \max(w_u, \text{len}(u)+1)\)

事實上，每次需要遍歷 \(\text{parent tree}\) 更新正是我們選擇最短串建 SAM 的原因

時間復雜度 \(O(\sum |s_i|)\)

CF1054F - Electric Scheme (二分圖求最大獨立集方案 - 布爾變量賦值法)

首先顯然有解，在每個火花 \((x_i, y_i)\) 處畫兩次 \((x_i, y_i, x_i, y_i)\) 即可

注意到可以將連一根長線拆成很多相鄰的短線，于是考慮將火花按分別按 \(x, y\) 坐標排序，相鄰火花間連線

令初始時答案為 \(2n\)，我們可以選擇合并一些線，每次合并答案會 \(-1\)，求最多能合并多少次

顯然，有沖突關系的線 (相交且不交于端點) 我們只能選 \(1\) 根；考慮直接在線間連邊刻畫沖突關系

問題轉化為對于點數(shù)為 \(O(n)\)，邊數(shù)為 \(O(n^2)\) 的二分圖求最大獨立集方案

考慮布爾變量賦值法：

• 給每個點賦布爾變量 \(x_i\)，以最小割為例，令 \(x_S = 1, x_T = 0\)

  若 \(x_i = 1\) 則 \(i\) 屬于 \(S\) 連通塊，\(x_i = 0\) 則屬于 \(T\) 連通塊

  則最小割可轉化為最小化 \(\displaystyle \sum_{(u_i \rightarrow v_i, w_i) \in E} w_ix_{u_i}(1-x_{v_i})\)

• 類似的，令 \(x_i = 1\) 表示選擇點 \(i\)，\(x_i = 0\) 表示不選

  則最大獨立集可轉化為最小化 \(\displaystyle \sum_{u \in V} -x_u + \sum_{(u_i, v_i) \in E} \infty x_{u_i}x_{v_i}\)

  考慮將最大獨立集的式子轉化為最小割的式子

  注意到 \(\infty x_{u_i}x_{v_i}\) 不好處理，我們希望將 \(x_{v_i}\) 變?yōu)?\((1-x_{v_i})\)；由于原圖為二分圖，可以將所有右部點取反

  具體的，對右部點，更改定義為 \(x_i = 1\) 表示不選點 \(i\)，\(x_i = 0\) 表示選；原式轉化為：

  \(\displaystyle \sum_{u \in L} -x_u + \sum_{v \in R} -(1-x_v) + \sum_{(u_i, v_i) \in E} \infty x_{u_i}(1-x_{v_i})\)

  \(\displaystyle = \sum_{u \in L} -x_u + \sum_{v \in R} x_v + \sum_{(u_i, v_i) \in E} \infty x_{u_i}(1-x_{v_i}) - |R|\)

  考慮將 \(-x_u\) 與 \(x_v\) 也轉化為 \(x_{u_i}(1-x_{v_i})\) 的形式，注意到 \(x_S = 1, x_T = 0\)，轉化為：

  \(\displaystyle = \sum_{u \in L} x_S(1-x_u) + \sum_{v \in R} x_v(1-x_T) + \sum_{(u_i, v_i) \in E} \infty x_{u_i}(1-x_{v_i}) - |L| - |R|\)

  常量扔掉，直接建模最小割即可：

  • 對 \(u \in L\)，連邊 \((S \rightarrow u, 1)\)

  • 對 \(v \in R\)，連邊 \((v \rightarrow T, 1)\)

  • 對 \((u_i, v_i) \in E\)，連邊 \((u_i \rightarrow v_i, \infty)\)

    事實上，易得這部分每條邊流量最大為 \(1\)，可以直接將容量改為 \(1\)，這樣 dinic 是 \(O(m \sqrt n)\) 的

那么直接 dinic 即可

跑完后 dfs 搜出 \(S\) 的聯(lián)通塊，最大獨立集方案即為：

• 滿足 \(u_i \in L\) 且 \(x_{u_i} = 1\) (在 \(S\) 的連通塊) 的 \(u_i\)
• 滿足 \(v_i \in R\) 且 \(x_{v_i} = 0\) (在 \(T\) 的連通塊) 的 \(v_i\)

時間復雜度 \(O(n^2 \sqrt n)\)

8.28

CF1416F - Showing Off (拆環(huán) + 二分圖 - 關鍵點優(yōu)先匹配)

對位置 \((x, y)\)，若存在相鄰位置 \((x', y')\) 滿足 \(b_{x', y'} < b_{x, y}\)，則可讓 \((x, y)\) 走到 \((x', y')\)，再用 \(a_{x, y}\) 補齊差值

顯然，若對所有相鄰位置都有 \(b_{x', y'} > b_{x, y}\)，則無解

那么難點只在于處理 \(b_{x', y'} = b_{x, y}\) 的情況；這實際上要求 \((x, y)\) 與 \((x', y')\) 在一個環(huán)內

注意到環(huán)長必為偶數(shù)，考慮拆成許多二元環(huán)處理，而二元環(huán)就相當于兩兩匹配

問題轉化為將滿足 \(b_{x', y'} = b_{x, y}\) 的 \((x', y')\) 與 \((x, y)\) 連邊，求最大匹配方案

但事實上，有些 \((x, y)\) 已經可以連到相鄰且小于它的位置，這種位置匹配不上也沒關系

我們稱必須匹配的點為 "關鍵點"，則我們需要讓關鍵點優(yōu)先匹配

有的先匹配有的后匹配做不了，考慮通過 "讓非關鍵點匹配機會變多" 降低其 "匹配優(yōu)先級"，具體的：

• 創(chuàng)建一些 "幻想點" 將左右部點數(shù)量補齊

• 在所有不是關鍵點的點 (即 "非關鍵點" 與 "幻想點") 間兩兩連邊

  這一步可以創(chuàng)建一個虛點優(yōu)化建圖

跑最大匹配，若不是完美匹配則無解，若是則搜出方案即可

時間復雜度 \(O(nm \sqrt{nm})\)

QOJ3555 - Chameleon's Love (觀察性質 + 二分圖獨立集)

部分分 1：所有戀慕關系都是雙向的

若選擇相互戀慕的一對變色龍，它們會互相交換顏色，不改變顏色總數(shù) (即顏色總數(shù) \(=\) 詢問集合大小)

那么顏色總數(shù)改變 \(\iff\) 選擇了至少一對顏色相同的變色龍

考慮對每個變色龍 \(i\) 二分一次，\(i\) 與 \(S\) 中的點有連邊 \(\iff\) \(\text{Query}(S \cup i) > \text{Query}(S)\)

詢問次數(shù) \(O(n \log n)\)

這個部分分啟示我們觀察什么時候顏色總數(shù)會改變

部分分 2：\(O(n^2)\) 次詢問

考慮對每兩只變色龍都問一次，若顏色總數(shù)為 \(1\) 則連邊

對變色龍 \(i\)，設 \(a_i\) 為 \(i\) 戀慕的變色龍，\(b_i\) 為戀慕 \(i\) 的變色龍，\(c_i\) 為與 \(i\) 同色的變色龍

顯然，\(i\) 只可能和 \(a_i, b_i, c_i\) 連邊

若 \(i\) 的度數(shù)為 \(1\)，則必有 \(a_i = b_i\)，此時 \(i\) 連向的點就是 \(c_i\)

若 \(i\) 的度數(shù)為 \(3\)，考慮分討詢問 \(\{i, a_i, b_i, c_i\}\) 子集的情況：

• \(\{i, a_i, b_i, c_i\}\)，則 \(i \rightarrow a_i\) 且 \(b_i \rightarrow i\) 且 \(i = c_i\)，顏色總數(shù)為 \(2\)
• \(\{i, a_i, b_i\}\)，則 \(i \rightarrow a_i\) 且 \(b_i \rightarrow i\)，顏色總數(shù)為 \(2\)
• \(\{i, b_i, c_i\}\)，則 \(b_i \rightarrow i\) 且 \(i = c_i\)，顏色總數(shù)為 \(1\)
• \(\{i, a_i, c_i\}\)，則 \(i \rightarrow a_i\)，顏色總數(shù)為 \(2\)
• \(\{i, a_i\}\) 與 \(\{i, b_i\}\) 與 \(\{i, c_i\}\) 顏色總數(shù)均為 \(1\)

容易發(fā)現(xiàn)情況 \(\{i, b_i, c_i\}\) 是特殊的，找出這種情況后將所有 \(i \rightarrow a_i\) 拿出來，用排除法找出 \(c_i\) 即可

詢問次數(shù) \(O(n^2)\)

這個部分分啟示我們重點關注 \(a_i, b_i, c_i\)

部分分 3：性別已知

在部分分 2 的基礎上，我們只需優(yōu)化詢問次數(shù)即可

對變色龍 \(i\)，考慮找與其性別不同的變色龍組成的集合 \(S\) 詢問

有了部分分 2 的啟發(fā)，容易發(fā)現(xiàn)只有 \(a_i, b_i, c_i\) 至少一個在 \(S\) 中時，顏色總數(shù)改變

那么可以通過 \(3\) 次二分找出 \(a_i, b_i, c_i\)，剩下的與部分分 2 相同

詢問次數(shù) \(O(n \log n)\)

正解：

考慮優(yōu)化部分分 3 的做法

注意到我們實際上不需要 \(S\) 中性別均相同，只需要 \(S\) 內部無連邊即可

這啟示我們維護二分圖獨立集

考慮增量構造，維護兩個獨立集 \(S_0, S_1\)，每次加入新節(jié)點 \(i\)

容易通過部分分 3 的方式對 \(S_0\) 與 \(S_1\) 分別詢問，二分出 \(i\) 與 \(S_0, S_1\) 中的點的所有連邊

由于 \(n \le 500\)，直接連無向邊，重新黑白染色構造出新的 \(S_0, S_1\) 即可

最終找到所有連邊后，可用部分分 2 的做法求出答案

詢問次數(shù) \(O(n \log n)\)，時間復雜度 \(O(n^2 \log n)\)