1 NFLS 模擬賽 T1

每個點處理一些信息，選好枚舉哪個點就行。

2 NFLS 模擬賽 T2

首先，所有 \(x_i+y_i\) 奇偶性相同是必要條件。其次，其也是充分條件。

觀察大樣例可以看出其給的是 \(1,2,4,8,\cdots\)，對這個東西構造即可。大概是你嘗試歸納證明用 \(2^0,2^1,\cdots,2^k\) 能表示出所有 \((a,b)\)，其中 \(0 \leq a, b \leq 2^{k-1}\)，題目的 \(40\) 限制是不緊的。

3 NFLS 模擬賽 T3

點分治單側遞歸，查詢時用長剖，這樣就是 \(O(n\log^2 n)\) 的。

我寫了，過不去。

注意到找到全局最長 LIS 鏈后，刪的點肯定在鏈上，從兩個端點出發做一次就是 \(O(n\log n)\) 的了。

4 QOJ8729

注意到問題等價于一個異或方程組，答案是 \(2^{m - \mathrm{rank}}\)。我們的目標是盡量減少異或方程數量。如果有 \(c\) 個這樣的限制，我們可以在 \(O(\dfrac{cm^2}{w})\) 的復雜度內求出答案，一個個插入線性基，bitset 維護即可。

考慮對于每個 \(u\)，求出以 \(u\) 為根的葉向生成樹。我們聲稱只需要考慮經過一條非樹邊的路徑的限制即可。所以總共有 \(O(nm)\) 個限制，復雜度 \(O(\dfrac{nm^3}{w})\)，足以通過。

這么做的正確性在于每條路徑都能被若干經過一條非樹邊路徑做對稱差得到，這是一個經典技巧。

5 P11986

這題很厲害。

四個角落不是很容易刻畫。觀察一些性質。一個點 \((x,y)\) 距離左上角為 \(x+y-2\)，距離右下角為 \(2L-(x+y)\)。所以不可能存在兩個點 \((x_1,y_1)\) 與 \((x_2,y_2)\)，使得 \(x_1+y_1 < x_2+y_2\)，而前者選的是右下，后者選的是左上。

假設左上為 \(1\)，右下為 \(4\)，右上為 \(2\)，左下為 \(3\)。也就是說，將所有點按照 \(x+y\) 排序，存在一個最優解存在一條分界線使得前綴都選的是 \(1,2,3\) 中的一個，后綴都是 \(2,3,4\) 中的一個。

左上右下并不特殊，左上右下也有這樣的限制。故如果我們按照 \(x-y\) 排序，有分界線使得前面選的是 \(1,2,4\) 中的一個，后綴選的是 \(1,3,4\) 中的一個。

枚舉這兩條分界線，所有點被劃分成了 \((1,2),(1,3),(2,4),(3,4)\) 四種，分別表示其可能處于的兩個角落。

對每個集合做一個 DP，求出第一種所選的總距離為 \(x\) 的情況下第二種的最小總距離 \(f_x\)。枚舉 \((1,2)\) 中 \(1\) 的總距離 \(x\)，得到 \((1,3)\) 中 \(1\) 的距離最大值 \(T-x\)，從而確定 \(2,3\) 在前兩組的距離最大值，然后就可以判定 \(4\) 是否符合條件。

直接這么做是 \(O(n^3T)\) 的，枚舉分界線是 \(O(n^2)\) 的，DP 是 \(O(nT)\) 的，但不難注意到枚舉第一條后只需要預處理前后綴的 DP 值就是 \(O(n^2T)\) 的，可以通過。

6 P10202

問題等價于，每次選一個連續同色區間刪去，問方案數。

考慮區間 DP。對于每個區間，轉移 \([l,r]\) 時我們希望考慮最后一次刪掉了一個同色段對應原序列的某個區間 \([l',r']\)，然后 \([l,l'),[l',r'],(r',r]\) 三部分獨立。為了計算方案數，顯然要計算這些操作序列拼在一起的方案數，故要記一個 \(k\) 表示操作序列長度。對于 \([l',r']\)，我們要求最后一次恰好刪去一個包含 \(l',r'\) 的子序列，所以考慮狀態 \(f_{l,r,k}\) 與 \(g_{l,r,k}\)，分別表示沒有要求與要求最后一次刪去了 \(l\) 與 \(r\) 的方案數。轉移是不難的，考慮最后一次刪了什么就行。復雜度 \(O(n^5)\)。

7 P10200

有經典結論：對于任意正整數 \(a<b<c\)，\(\min(a\oplus b, b\oplus c) \leq a \oplus c\)。

故任選兩個 \(\oplus\) 的最小值只需考慮排序后相鄰兩項。

據此設計 DP。將序列排序后記 \(f_{i,j}\) 表示 \([1,i]\)，\(a_i \in S_1\)，上一個 \(\in S_2\) 的數為 \(j\) 的方案數。轉移容易通過 01-Trie 進行優化，復雜度 \(O(n(\log n+\log V))\)。

8 P10203

圓方樹上做換根 DP 就行。不用帶什么腦子不過可能要想清楚細節。

9 P10284

平衡樹有交合并模板，過程等價于維護一個變量 \(s\) 初始為 \(0\)，每次若 \(s \leq 0\) 則 \(s \gets s + a_i\) 否則 \(s \gets s - a_i\)，離線下來做插入標記回收就行。\(a\) 單調不增好像不是很有用。

10 煉石 NOIP R11T1

不講。

11 煉石 NOIP R11T2

倒著從 \(n\) 到 \(1\) 做，簡單 DP，轉移注意前綴和優化一下。

12 煉石 NOIP R11T3

不難看出求的是一個樹的拓撲序計數狀物。

如果直接維護對偶圖其實有點難，但是考慮到若詢問點為 \(x\)，一條對角線 \((l,r)\) 對應的一側子樹大小只和 \(x\) 在 \((l,r)\) 哪一側有關。所以這個過程是容易線段樹維護區間乘單點查即可解決的。

13 煉石 NOIP R11T4

also known as JOI 2024 Final Road Service 2。

問題顯然等價于有若干區間，每次詢問選定其中若干個。在每個位置選擇花費 \(1\) 或 \(2\)，用盡量先少的花費使得選定的連通。

首先選定的可以視作兩兩沒有包含關系。按照 \(l\) 排序后 \(r\) 也遞增。

考慮 \(c=1\)。這個過程看起來只能貪心。大概就是第一個打通的肯定是第一個區間右端點，然后從前往后考慮每個區間，如果現在連通塊右端點還沒有下一個右端點大，那就只能選目前連通塊右端點。否則應該選下一個不屬于連通塊的詢問區間的右端點。這個過程可以倍增優化。

\(c=2\) 時，注意到如果我們考慮答案為 \(ans\)，顯然我們只關心 \(ans-1\) 與 \(ans\) 的狀態，因為更小的顯然不會更優。維護這兩種花費對應的目前連通塊最靠右的位置，倍增時處理一下，做法應該是類似的。

14 P14134

我有一個很神奇的做法。

具體來說，直接分治時，我們不方便判定 \(0\) 到底在哪一側，原因顯然是分出來的兩部分的返回值可能相同。

考慮維護兩個候選集合，滿足這兩個候選集合的第一類詢問結果相同，均為 \(s\)。記這兩個集合分別為 \(S_1\) 與 \(S_2\)。則我們知道這兩個集合有一個 \(\mathrm{MEX}\) 為 \(s\)，另一個 \(\min\) 為 \(s\)。

每次分治出 \(S_{1,0},S_{1,1},S_{2,0},S_{2,1}\)，并分別詢問 \(S_{1,0}\) 和 \(S_{2,0}\)。注意到若有其中一個結果小于 \(x\) 則意味著那一側應該是符合要求的。否則新的 \(S_1\) 和 \(S_2\) 分別為兩側中詢問值為 \(x\) 對應的那部分，即如果 \(S_{1,0}\) 詢問結果是 \(x\) 則新的 \(S_1\) 是 \(S_{1,0}\)，否則是 \(S_{1,1}\)。

這個次數大概是 \(2\) 次詢問可以除以 \(2\)，總次數 \(2\lceil \log_2 n\rceil\) 附近，測試出來只有 \(33\) 次。

15 P14135

先做一個子樹的情況。

注意到如果只有操作 \(1\)，顯然要求每個點有 \(a_u \geq a_{fa_u}\)，答案是 \(\sum a_u - a_{fa_u}\)。

對于 \(2\) 操作，我們先從下往上調整使得 \(a_u \geq a_{fa_u}\) 成立，然后考慮什么樣的操作能獲得正收益。

不難看出，令 \(d_i\) 為深度為 \(i\) 的點數，對深度為 \(i\) 進行操作的收益為 \(d_i-d_{i+1}-1\)。那么對這個從深到淺貪心即可。

對于原問題，每個子樹答案和深度有關。長鏈剖分優化即可。我沒寫。

16 P12448

由于增量是 \(1\) 所以你找到左右第一個比這個位置大的，然后就是做 \(O(1)\) 次區間加等差數列，單點查詢，直接做就行。

17 P12587

一個點的權值是前后綴 \(\max\) 的較小值減去其自身對 \(0\) 取 \(\max\)。

注意到前后綴 \(\max\) 中有一個是全局 \(\max\)，所以找到全局 \(\max\) 后就是前后綴問題。

這很容易用單側遞歸線段樹做，復雜度 \(O(n \log^2 n)\)。

18 P12619

這都是啥。

總而言之就是你要做 \(n=200\) 的一般圖最大權匹配。我也不會做，找個板子拉下來就行了。

19 CF2128E2

注意到一個區間 \([l,r]\) 向左或右加入或刪除一個數，中位數覆蓋到的集合是連續的。

找到最小和最大中位數對應區間，類似莫隊擴展就行了。

找最小和最大容易二分。復雜度 \(O(n\log n)\)。

20 NFLS 模擬賽 T1

不講。

21 NFLS 模擬賽 T2

不講。

22 NFLS 模擬賽 T3

這個問題不難轉化成形如最大權 \(k\) 重區間覆蓋問題，跑費用流就行。寫 SPFA 是 \(O(mn^2)\) 的，能過。更有道理的就寫個原始對偶。

23 NFLS 模擬賽 T4

做過一萬遍了，不寫了。

24 P11712

問題為，給你一個連通圖，問是否有方法刪掉不多于兩條邊使其變為一個二分圖，并輸出達到最小的方案數。

DFS 樹是解決無向圖問題的有力工具。

先考慮判定是否存在方案刪去一條邊使其變為二分圖。

眾所周知一個圖是二分圖等價于任意一個回路長度為偶數。另一方面，一個圖的所有回路是 DFS 生成樹的非樹邊直接形成的簡單環進行對稱差所生成的。考慮刪掉一條邊，若其為非樹邊，要求其是唯一一條形成奇環的非樹邊。若其為樹邊，要求經過其的非樹邊構成的環都是奇環且所有非樹邊構成的奇環均經過這條邊。后者顯然必要，前者的必要性在于，若同時存在一個奇環和偶環經過這條邊，對稱差后得到了一個不經過這條邊的長度為奇數的回路。不難證明這同樣是充分條件。

若必須至少刪去兩條邊 \(e_1,e_2\)，考慮若分別存在兩個非樹邊構成的奇環和偶環同時經過 \(e_1\) 與 \(e_2\)，則對稱差后得到了一個不經過 \(e_1,e_2\) 的奇環。另一方面，若存在兩個非樹邊構成的奇環和偶環只經過 \(e_1\) 不經過 \(e_2\)，則也得到了一個不經過 \(e_1,e_2\) 的奇環。

基于上述事實，進行一些分類討論，不難得到，刪去兩條邊 \(e_1\) 與 \(e_2\) 合法當且僅當在只考慮偶環時這兩條邊切邊等價，且包含他們的非樹邊奇環集合構成了所有非樹邊奇環集合的無交劃分。

上述過程容易用異或哈希解決。

25 P11391

一個長度至少為 \(3\) 的回路雙射成對偶圖的一個連通塊。問題等價于樹的連通塊計數。

26 P11432

注意到若區間 \([l,r]\) 中第一次激活的是某個位置 \(x \in (l,r)\)，則不如之前在 \(l\) 或 \(r\) 時停在那里等待，直到時間到了再走。

所以問題等價于 \(O(n)\) 個限制 \(x_i,t_i\)，表示 \(x_i\) 激活時間大于等于 \(t_i\)。

此外，考慮類似時間軸掃描線，坐標維上用一個 \(01\) 字符串表示每個位置是否已經被激活。則任意時刻，\(1\) 的位置一定是一段前綴與后綴的并。因為若中間某個位置激活了而兩邊沒有激活，可以改為等到最后一次經過這個點時再激活。

綜上，容易區間 DP 計算答案。復雜度 \(O(n^2)\)。

27 煉石 NOIP R12T1

不講。

28 煉石 NOIP R12T2

一看就是根號分治狀物。

\(k \geq \sqrt{n}\) 時直接做就行。

\(k<\sqrt n\) 時，我們希望對于每個 \(r,x\) 都計算出 \(\sum \limits_{i\equiv r \pmod k} \dbinom{i}{x}\)，記答案為 \(s_{r,x}\)，注意到組合恒等式 \(\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\)，且有 \(k\mid n\)，所以 \(s_{r,x} = s_{r-1,x-1}+s_{r-1,x}\)。\(r=1\) 時需要特判一下，因為最后的第 \(n\) 與 \(n-1\) 項應該是不存在的。

現在只需要能求出 \(s_{0,x}\) 就行，即對于所有 \(x\) 求出 \(\sum \limits_{i} \dbinom{ik}{x}\)，記為 \(f_x\)。

考慮到 \(\dbinom{n+k}{x} = \sum \limits_{i=1}^k \dbinom{k}{i}f_{x-i}\)。這個是容易通過兩邊做差歸納證明的。所以可以在 \(O(nk)\) 的復雜度內遞推出 \(f_x\)。總復雜度 \(O(n \sqrt n)\)。

29 煉石 NOIP R12T3

缺一分治模板，注意到可以在 \(O(n^2)\) 的復雜度內激活一個點，所以缺一分治復雜度就是 \(O(n^3\log n+q)\)。空間是 \(O(n^2\log n)\) 的。

30 煉石 NOIP R12T4

BST 等價于 \((p_i,i)\) 的小根笛卡爾樹。

你把每個點 \((p_i,i)\) 畫在平面直角坐標系中，問題就轉化為了 \(n=5000\) 量級的最優二叉搜索樹問題。這個問題是有四邊形不等式的，復雜度 \(O(n^2)\)。

31 P11593

很詭異的一個題。

二分答案 \(k\)，把過程反過來，問的就是是否存在一條邊界開始的路徑，第 \(i\) 個點權值 \(\geq k - i+1\)。

注意到如果在相鄰兩個點之間連一條邊權為點權較小值的邊，則我們只需要在 Kruskal 重構樹上走來走去。對這個東西 DP 就行了。復雜度 \(O(nm \log nm)\)。

32 P11197

經典的 \(O(n \log n)\) 三維偏序模板。

具體來說，我們對于 \(i,j\)，考慮 \(S_{i,j} \subseteq \{0,1\}^3\)，表示每一維是否有 \(i\) 小于 \(j\)。即求 \(\sum \limits_{i \neq j} [S_{i,j}=\{1,1,1\}]\)。

注意到 \(S_{i,j} = \{1,1,1\}\) 與 \(S_{i,j} = \{0,0,0\}\) 數量相同。做一個容斥就會發現你只需要做 \(3\) 次二維偏序了。

33 P11241

點分樹優化建圖模板。

34 ARC151E

如果 \(X,Y\) 最長公共子串長度為 \(l>0\)，答案即為 \(|X|+|Y|-2l\)。用你喜歡的方式求最長公共子串即可。

考慮 \(X,Y\) 最長公共子串為 \(0\)，這個題的限制非常的不自然，要求 \(X\) 在操作時非空。所以先考慮 \(|X|=1\) 的情況。不難發現目標就是盡量快地令 \(X\) 成為 \(Y\) 的某一個字符。這個東西建圖跑最短路就行。

\(|X|>1\) 是一樣的，操作肯定是找到某個字符然后刪 \(X\) 變為那一個字符。直接做就行。

注意到最短路本質上是邊權相同的，所以瓶頸是最長公共子串，所以顯然可以做到嚴格線性，不過不重要。

35 ARC207C

就是說分成盡量多區間使得每個區間的或非嚴格遞增。

這個是經典套路。顯然只有 \(O(n \log V)\) 個狀態，編一個小于 \(O(n\log^3 V)\) 的就可以通過。我的是 \(O(n\log^2 V\log \log V)\) 的。

36 ARC207A

注意到 \(\sum \limits_{i=1}^n \min(i-1,a_{p_i}) = \sum \limits_{i=1}^n \sum \limits_{j=i+1}^n [a_{p_j} \geq i]\)，從后往前 DP 就行。復雜度 \(O(n^4)\)。

37 ARC156D

根據 Lucas 定理，每個 \(a_i\) 的出現次數 \(c_i\) 構成 \(k\) 的一個二進制劃分。

問題變為對 \(k\) 二進制下的每個 \(1\) 分配一個 \(a_j\)，貢獻是 \(a_j \times 2^i\)，求貢獻和的異或和。

從后往前 DP，注意到 \(a \leq 1000\)，所以往前貢獻不超過 \(10\) 位，把往前貢獻的值記錄到 DP 狀態中即可。復雜度 \(O(na \log k)\)。

38 ARC165E

這個題很有趣。

整個問題是動態的，很難刻畫，任意時刻你甚至都不知道有多少個點滿足其連通塊內點數 \(>k\)，所以不好做。

對于這種選點要符合限制，且限制和之前決策有關的問題，嘗試把限制去掉。具體來說，我們將操作改成每次任意選一個點，如果其所屬連通塊大小大于 \(k\)，將其刪去并對次數貢獻 \(1\)，否則跳過。顯然一個點被選多次沒有意義，所以問題可以轉化為求所有 \(1\) 到 \(n\) 的排列的貢獻次數和。

到這一步還是不好做。此時考慮為每次有效操作欽定代表元進行計數，具體來說我們將每次有效操作的貢獻記錄在其所選點的那個連通塊上。那么我們要計算原樹上每個連通塊在某次操作中被選的概率和，即為答案。

對于一個大小為 \(x\) 的連通塊，若其被貢獻要求 \(x>k\)，令連通塊外面掛著 \(y\) 個點，則相當于排列 \(p_1,\cdots,p_n\) 中這 \(y\) 個數中任意一個數都出現在 \(x\) 個數之前。概率為 \(\dfrac{x!y!}{(x+y)!}\)。

對原樹任意選根，每個連通塊在其頂端進行貢獻。這樣就可以直接做子樹 DP 了。\(f_{i,j,k}\) 表示 \(i\) 為根的連通塊，大小為 \(j\)，外面掛了 \(k\) 個點的連通塊數量。這樣復雜度就是 \(O(n^4)\) 的了。

39 P14176

這種題都不會做，沒救了。

令每一行或列的狀態為其最后一次操作所覆蓋的顏色。

一個 \(k\times k\) 子矩形合法，當且僅當其對應的行的狀態都是 \(1\)，且列被染 \(0\) 的最晚時間小于行染 \(1\) 的最早時間，或者把行列反過來。

這個直接樹狀數組維護就好了。

40 P14177

先做 min-max 容斥，變為求所有 \(S\) 的 \((-1)^{|S|-1}E(\min \limits_{i\in S} T_i)\) 的和。

對于 \(S\)，假設有 \(x\) 個 chkmax 操作會使得 \(S\) 內某個 \(i\) 變為合法，則其成功率為 \(\dfrac{x}{m}\)，期望次數即為 \(\dfrac{m}{x}\)。令 \(g_S = x\)。

我們只需要對每個 \(x\)，求所有滿足 \(g_S=x\) 的 \(S\) 的 \((-1)^{|S|-1}\) 和即可。

考慮區間 DP。\(f_{l,r,x}\) 表示只考慮區間 \([l,r]\) 內所有滿足 \(a_i \geq a_{l-1}\) 且 \(a_i > a_{r+1}\) 的點與包含于這個區間內的 chkmax 操作時的答案。轉移枚舉區間中被選入 \(S\) 的 \(a\) 的最小值，則左側都大于他，右側都大于等于他，跨過這個點的區間數量容易算出，復雜度 \(O(n^3m^2)\)。

可以拉插優化，把 \(f_{l,r}\) 看作多項式帶點值進去算即可。

42 NFLS 模擬賽 T2

分塊并查集即可通過，跑得飛快。離線下來每個塊單獨做即可做到線性空間。

但這個題其實可以 polylog，非常厲害。

考慮對于每個數 \(x\)，維護 \(01\) 序列，每個位置 \(i\) 表示 \(a_i \geq x\) 是否成立。

修改只需要做可持久化線段樹分裂合并，查詢做線段樹二分即可。

43 NFLS 模擬賽 T3

你覺得這是題嗎。

沒有 \(01\) 個數限制那么令 \(s_i = \mathrm{popcount}(i)\) 即可，滿足相鄰兩個數權值不同。

對于原問題。考慮若存在映射 \(f_i\)，滿足相鄰兩個基本不變。那么令 \(s_i = f_i \oplus \mathrm{popcount}(i)\) 即可。

注意到限制為 \(\lceil \sqrt n \rceil\)，考慮分塊。令 \(f_i=1\) 當且僅當 \(i\) 存在某一塊全 \(1\)，不難說明確實符合條件。

44 NFLS 模擬賽 T1

考慮 DP，直接轉移是 \(O(nm^2)\) 的，但是不難看出可以用個單調隊列就可以做到 \(O(nm)\)。

45 NFLS 模擬賽 T2

這個題很簡單的，你只需要對于每個樹上的點記錄其對應第二棵樹上的哪個連通塊，以及對應的連通塊中的點是哪個。雖然看起來有 \(O(n2^m)\) 個狀態轉移還得做無交并卷積，但是注意到每個點上保留的狀態必然是一個向外至多一條出邊的連通塊，所以根本跑不滿。

46 NFLS 模擬賽 T3

相信大家都做過排列值域連續子段計數，做法是注意到區間 \(\max - \min \geq r-l\)，且當且僅當值域連續時取等。

對于這個題，你對交的部分掃描線就行。看起來就是可做的，分析一下也是可做的，帶著單調棧做掃描線線段樹上維護一些信息就行。

47 ARC148E

牛完了。

對于排列計數，常見考慮方式有連續段 DP，或者按照某個順序插入能做到沒有后效性地確定每次插入的方案數。當然也可以考慮按照序列維依次加入并插入到之前的位置，或者考慮雙射等一般計數手法。

但這個題好像每個都不太容易做。這就不得不提起相鄰兩個數和大于等于 \(k\) 的經典處理技巧了。我們將小于 \(\lceil \dfrac{k}{2} \rceil\) 的數記為 \(0\)，將大于等于的記為 \(1\)。\(1,1\) 相鄰肯定符合條件，\(0,0\) 相鄰必定不符合，而 \(0,1\) 相鄰則取決于具體值是什么。

現在考慮按照某個順序插入所有數使得插入沒有后效性，并且一個排列合法當且僅當其按照插入順序依次插入滿足任意一個前綴時間合法。注意到如果我們按照 \(k,0,k-1,1,k-2,2,\cdots\) 的順序依次插入所有數，則插入一個 \(1\) 時，要求是不能和之前的 \(0\) 的相鄰。而插入一個 \(0\) 時，限制竟然也是不能和 \(0\) 相鄰。而 \(0\) 本來就兩兩不相鄰，所以空位數就是 \(l+1-2c\)，和之前的插入方式完全無關。并且不難驗證這個插入順序每個前綴都合法等價于排列合法。

復雜度 \(O(n \log n)\)，瓶頸在于排序。

這個題的精妙之處在于，想到按照這個順序插入不依賴之前的決策，這個確實很厲害。

48 ARC136E

先刻畫 \(i<j\) 滿足 \(i\) 能走到 \(j\) 的條件。令 \(p_x\) 為 \(x\) 最小質因數。

首先 \(i,j\) 同為偶數必然可行。

否則，若 \(i\) 為奇數，\(j\) 為偶數，則 \(i\) 能到 \(j\) 當且僅當 \(i+p_i \leq j\)。\(i,j\) 同為奇數，當且僅當 \(i+p_i \leq j-p_j\)。

首先我們可以發現，最小的 \(y\) 使得 \(y>x\) 且 \(\gcd(x,y)>1\) 的 \(y=x+p_x\)，證明顯然。且 \(x\) 是奇數則 \(p_x\) 一定也是奇數，故 \(x+p_x\) 為偶數，所以上述條件的充要性不難推出。

考慮若反鏈存在偶數，枚舉其為 \(2 \mid x\)。此時選的其余奇數若有 \(y<x\)，則 \(y+p_y > x\)，若 \(y>x\) 則 \(y-p_y < x\)。事實上發現這個東西不僅能保證其他數與 \(y\) 互相不能到達，也能保證其余奇數內部互相不能到達，分類討論這些奇數與 \(y\) 的大小關系即可。所以枚舉 \(x\) 后能取得的最大權值容易計算。

所有數都是奇數時，不難發現類似地存在一個 \(x\) 使得小于等于其的和大于其的在這個點分開，所以也是直接計算即可。

49 ARC127D

這個題相對簡單。

枚舉一個位 \(x\)，計算 \(a_i \oplus a_j\) 與 \(b_i \oplus b_j\) 在 \(x\) 之前的位相同，但這一位不同時的答案。令 \(a'_i,b'_i\) 為 \(a_i,b_i\) 在 \(x\) 之前的位的答案，則要求 \(a'_i\oplus b'_i = a'_j \oplus b'_j\)，且 \(a_i,a_j\) 在這一位下的相等情況與 \(b_i,b_j\) 不同。將 \(a'_i\oplus b'_i\) 劃分為等價類后不難計算答案。復雜度 \(O(n\log^2 V)\)。

50 ARC124E

我們非常希望能對于所有 \(b_i \in [0,a_i]\) 計算 \(\prod (a_i-b_i+b_{i-1})\)，但是這個答案顯然會算重。

不過注意到任意一個合法的最終序列 \(x\) 都對應到一個存在某個 \(b_i=a_i\) 的 \(b\) 序列，證明顯然。

對這個東西計算就不難了。用 \(b_i \leq a_i\) 減去 \(b_i < a_i\) 的答案即可。

\(b_i \leq a_i\) 怎么做呢。即求 \(b_i \in [0,a_i]\) 時 \(\prod (a_i-b_i+b_{i-1})\) 的和。每個 \(i\) 可以取 \(a_i,-b_i,b_{i-1}\)，先忽略環的問題，從前往后 DP 即可。對于環，枚舉 \(1,n\) 的情況從 \(1,n\) 處斷環為鏈即可。

51 P12729

枚舉 \(a\) 中的子串開頭位置 \(i\)，不難求出最大的 \(j\) 滿足 \(a[i\cdots j]\) 在 \(b\) 中出現過。這個容易通過后綴數組算出。

然后在 \([i, j]\) 中找到最靠后的 \(x\) 使得 \([i,x]\) 括號匹配也是不難的，這個預處理前綴和與單調棧就能算。

寫個線性后綴數組就可以做到嚴格線性。

52 P12653

好像是個點分治模板，不用帶腦子。

53 P11127

這個題比較簡單。

顯然就是說你要計算到根路徑上是左兒子的 \(-1\) 與是右兒子的 \(0\) 與 \(-1\)。

而修改是編號的連續段，查詢是到根路徑，經典是不能 polylog 的。對序列分塊，然后直接就做完了，可能需要平衡一個分塊做區間加什么的，但都是簡單的。

54 P12969

一個序列合法當且僅當總和為 \(n-1\)，且將每個數減 \(1\) 后除了全局外每個前綴和都非負。

找到全局最靠左的前綴和最小值點，不難注意到如果循環位移開頭在其左側，則必然不可行，因為這意味著中間這一段的和為負數。若在后面，則后綴和大于等于 \(-x\)，\(x\) 為最小前綴和。若是這樣，則 \(x\) 開始存在一段后綴的前綴滿足和是負數，與 \(x\) 為最小前綴和矛盾。故最多只有一個這樣的點，位置就在 \(x\)。然后都是容易維護的。

55 P11704

肯定有一條路徑經過 \((1,2)\) 與 \((n-1,m)\)，另一條經過 \((2,1)\) 與 \((n,m-1)\)。

路徑不交限制太難受了，LGV 引理轉化為沒有限制。

然后相當于計算有多少兩條路徑，滿足第一條從 \((1,2)\) 到 \((n-1,m)\)，第二條從 \((2,1)\) 到 \((n,m-1)\)，且經過所有關鍵點。

將關鍵點按 \((x,y)\) 二元組排序，可以把路徑的過程按照時間寫成若干個 \((i,j,0/1)\)，表示已經走完了 \([1,i]\) 之間的所有點，一個結束在 \(i\)，另一個結束在 \(j\)，且 \(i,j\) 對應的是 \((1,2),(2,1)\) 開始的還是相反的。DP 容易轉移，復雜度 \(O(k^2)\)。

56 P10052

有一個基于值域的 DP。\(f_{i,0/1,0/1}\) 表示目前在時刻 \(i\)，所處第一個還是第二個教室，另一側的教室這個時刻所放的之前有沒有看過。轉移是容易的。

使用經典技巧值域定義域轉換就做完了。

口胡的，假了踢我。

57 P7828

首先答案是逆序對數。

注意到交換操作是交換相鄰兩個，所以對逆序對的貢獻只有這兩種數對應的逆序對。

考慮根號分治。設閾值 \(B\)。將所有數稱為小數或大數，分別表示其出現次數小于等于或大于 \(B\)。

考慮所有逆序對，分別是小數對小數，小數對大數，與大數對大數。

小數對小數與小數對大數都可以在修改的時候直接做。而我們可以預處理任意兩個大數之間的貢獻。復雜度看起來是 \(O(n\sqrt n)\) 的。

58 P12923

首先暴力擴展就是調和級數的，具體來說維護目前極長前綴，每次選起點小于等于前綴 \(+1\) 位置的一個子串向后。每個點只會被至多兩個子串包含，復雜度是調和級數的。

然后問題在于求那個小于等于某個位置開頭的子串。上一些后綴結構或者在失配樹上做就是 \(O(n\log^2 n)\) 的，不夠優秀。

注意到如果我們能正著和反著處理 Z 函數，按照前綴長度掃描線就能直接做序列并查集了。復雜度 \(O(n \log n \alpha(n))\)。

59 P12768

競賽圖縮點是鏈，只要能縮點就好了。

有一個直接數據結構優化建圖的做法，但是空間限制太低了肯定過不去。

考慮將所有數按照其之間直接的邊的順序排序。這不是一個偏序關系所以你可能要手寫一個排序。得到這個排列后必定滿足每個 SCC 是一個區間，這是顯然的。

問題變為劃分出所有 SCC。從前往后嘗試依次求出每個 SCC，即目前已經求出了 \([1,i]\)，找到最小的 \(j\) 滿足 \((i,j]\) 向 \([j+1,n]\) 的邊都是后面指向前面的。這個問題只需依次枚舉 \(j\)，要求的是所有比 \(j\) 更劣的點都在后面，也就是求兩個序列前綴交的最大值，這個東西可以線段樹做，而過程是可以離線的所以空間是線性的。大概應該是這么做的。

60 CF1866E

沒看懂這個題在考察什么。

顯然只有 \(O(q^3)\) 個狀態，每個前綴只有 \(O(q^2)\) 個狀態。然后轉移直接枚舉之前的狀態就做完了啊。

61 NFLS 模擬賽 T1

倒著做就是經典的直徑合并問題。并查集維護每個連通塊的直徑端點即可。

62 NFLS 模擬賽 T2

枚舉每種顏色，計算以其為嚴格眾數的區間個數。將等于這個數的位置設為 \(1\)，不等于的設為 \(-1\)，即求有多少區間和嚴格大于 \(0\)，帶 \(\log\) 做法是很容易的，過不去。

正解應該是說注意到前綴和數組是形如若干斜率為 \(-1\) 的線段拼在一起，所以有意義的位置只有線性個，可以線性維護的。

63 NFLS 模擬賽 T3

單調隊列優化 DP。

64 ARC140D

最終圖的形態是基環樹森林。所以連通塊個數等于環的個數。

先把給的邊連了，那么每個連通塊是基環樹或樹。基環樹一定會產生恰好 \(1\) 的貢獻，而每棵樹有一個點可以向任意點連邊。欽定 \(k\) 個位置成環，貢獻就是 \((k-1)!\prod s_i\)，直接 DP 就行。

65 ARC138D

首先一個排列合法，將所有數異或上任意數 \(x\) 后均合法。

\(2\mid k\) 顯然無解，\(k=1\) 顯然有解。

如果 \(k=n-1\) 有解，我們不難通過截取后 \(k+1\) 位和前面分開，前面做 \(k=1\)，后面做 \(k=n-1\) 即可。

\(k=n-1\) 怎么做呢。注意到每次枚舉一個 \(\mathrm{popcount}=n-1\) 將目前的值異或上他，若不在集合內則加入，可以構造出所有 \(k=n-1\) 的答案。然后就做完了。

66 ARC158E

分治就做完了。復雜度 \(2\) 個 \(\log\)。

67 ARC127E

先考慮怎么判定一個集合 \(S\) 是否可能成為最終集合。

考慮倒著處理每個操作。遇到 \(1\) 時，刪去集合中任意一個數。遇到 \(2\) 時，向集合中加入一個比目前最大值大且沒出現過的數。

貪心的，遇到 \(1\) 肯定移除集合中最大值。\(S\) 合法當且僅當每一次操作 \(2\) 都能成功刪去一個數。

考慮將整個操作過程分段，每一段是一個極小區間使得區間中 \(1\) 比 \(2\) 多一個。每個區間恰好依次刪去了 \(S\) 中從大到小的所有數。對這個過程進行 DP，每次往下一個區間時欽定新的被刪去的最大值即可。復雜度 \(O(n^2)\)。

68 煉石 NOIP R14T1

每位單獨算就可以換根 DP 了。

69 煉石 NOIP R14T2

唐氏癥題。

注意到對于一個長度大于等于 \(5\) 的序列來說，令所有數的最高位為 \(2^k\)，有 \(c\) 個數包含這一位。則若 \(2 \mid c\)，答案為 \(0\)，否則答案為 \(2^k\)。枚舉最高位將所有數看作 \(0,1,-1\) 即可。

對于長度小于 \(5\) 的區間，暴力。

70 煉石 NOIP R14T3

顯然二進制數可以用線段樹模擬。為了比較大小維護一下哈希即可。

當然你也可以用 set 做顏色段均攤，都能做的。

71 煉石 NOIP R14T4

直接 DP 需要記錄樹高，點數等一堆信息，狀態數很大。考慮一步步分析性質。

我們嘗試按照子樹深度大到小依次確定樹的形態。初始時，有一個點為根，子樹深度未知，不妨記為 \(h\)。第二步，其會產生兩個兒子，深度同時是 \(h-1\) 或一個為 \(h-1\) 另一個為 \(h-2\)。可以發現任意時刻我們只關心兩種子樹深度的點。假設現在深度為 \(h\)，我們關心有多少個點深度為 \(h-1\)，有多少個點深度為 \(h-2\)，分別記為 \(x,y\)，則之后枚舉 \(x\) 個點有多少產生了不同深度的兒子就能轉移到下一步狀態。具體來說，如果現在狀態是 \((h,x,y,k)\)，枚舉 \(c\) 個 \(x\) 轉移成了 \((h-1,h-1)\)，\(x-c\) 個 \(x\) 轉移成了 \((h-1,h-2)\)，則新的狀態變為 \((h-1,y+x+c,x-c,k+x-c)\)。可以發現 \(k\) 這一維其實是 \(y\) 這一維歷史上所有狀態的和，所以 \(y\) 和 \(k\) 都是 \(O(k)\) 量級。\(h\) 是 \(O(\log n)\) 的，這是因為這個東西本質上是個 AVL 樹。直接做大概是 \(O(nk^3 \log n)\) 這樣的。

然后你考慮從葉子開始往上。假設最后有 \(x\) 個葉子，有 \(y\) 個點滿足其有一個兒子為空另一個兒子不為空，即子樹深度為 \(-1\) 的點數。則 \(2x+y-1=n\)，原因是一棵每個點都有兩個兒子的二叉樹若有 \(c\) 個葉子則有 \(2c-1\) 個節點。對于原樹，把 \(y\) 個點也算進來后減 \(y\) 就得到 \(n=2(x+y)-1-y=2x+y-1\)。

現在枚舉 \(y \leq k\)，得到了 \(O(k)\) 個狀態。考慮倒著如果倒著做，\((x,y,k)\) 怎么向前推 \((x',y',k')\)。枚舉 \(c\) 后有 \(x'-c=y\)，故 \(x'=y+c\)，由 \(y'+x'+c = x\) 得 \(y'=x-x'-c=x-c-(y+c)=x-y-2c\)。而 \(k=k'+x'-c=k'+y\) 得 \(k'=k-y\)。故 \((x',y',k')=(y+c,x-y-2c,k-y)\)。我們有 \(x-y-2c \geq 0\)，所以 \(c \leq \dfrac{x-y}{2}\)，\(x'=y+c\leq y+\dfrac{x-y}{2}=\dfrac{x+y}{2}\leq \dfrac{x+k}{2}\)。注意到每次 \(x\) 近似于除以 \(2\)，最多只會多個 \(\dfrac{k}{2}\)，所以狀態數上界應該是 \(O(k^3 \log n)\) 的，轉移復雜度 \(O(k^2)\)，原因是里面其實還帶個組合數需要計算，總復雜度 \(O(k^5 \log n)\)，出題人說過了那就是過了。

72 P13990

這顯然是個基環樹，那你直接對每個子樹維護所有存在的點的深度做啟發式合并就做完了。

73 P14068

對塔做 DP。\(f_i\) 表示前綴答案，轉移考慮枚舉上一個 \(j\)，需要計算區間 \([j,i]\) 的權值。每個塔對應的是一個上凸的 \(+1\) 與 \(-1\) 斜率拼接狀物。這個東西是容易預處理的。

74 P13342

你要做的就是 kruskal 重構樹上求這些點兩兩 LCA 的并的點權和。

這玩意你考慮怎么做。對于每個點 \(u\)，什么樣的區間 \([l,r]\) 不會算到這個點，當且僅當區間內只存在左子樹或右子樹但卻不存在另一側的，或者壓根就不包含這個子樹內的任何一個點。這個和 NOIP T4 的那個啟發式合并做法很像。你維護每個點子樹內的編號連續段，然后啟發式合并就行。總共得到 \(O(n \log n)\) 個關鍵區間，之后的問題是簡單的，復雜度 \(O(n \log^2 n)\)。

75 P13523

先將序列全都減去極大值，然后詢問都是加正數。

令 \(f_i\) 表示長度為 \(i\) 的區間最大和，則答案為 \(\max \limits_{i} \{f_i+xi\}\)，只需要保留 \((i,f_i)\) 構成的凸包就行。

怎么求 \(f\) 構成的凸包呢。考慮分治。對于 \([l,mid]\) 和 \((mid,r]\)，算出每個前后綴和，由于只需要求 \(f\) 的凸包所以你也只需要保留前后綴和中的凸包，然后做閔可夫斯基和就行，就是你把差分的向量按照斜率歸并。這個閔和可以線性求，總復雜度 \(O((n+q)\log n)\)。

這個題數據很菜。我把閔和換成 \(O(n^2)\) 的暴力 \((\max,+)\) 卷積都過了。

76 NFLS 模擬賽 T1

把關系建成 DAG，拓撲排序即可。

77 NFLS 模擬賽 T2

難點在于刪點最短路。

這個做法很多。最簡單的做法應該是你直接做 LIS 計數，模質數后判定結果是否等于全局 LIS 個數即可。

也有確定性做法，你按值域從小到大加點維護前綴和后綴 LIS，加入一個點是不難做修改的。

78 NFLS 模擬賽 T3

看著就是關于 \(k\) 凸的。wqs 二分然后做反悔貪心即可。

關于為什么是凸的。考慮費用流。\(S\) 向每個點連 \((1,a_i)\)，每個點 \(i\) 向 \(i+1\) 連 \((+\infty, 0)\)。每個點向 \(T\) 連 \((1,b_i)\)，流量為 \(k\) 的最小費用流就是答案，所以是凸的。

79 NFLS 模擬賽 T4

注意到答案為第一棵樹上存在但第二棵樹上不存在的邊數。每次刪掉這樣的一條邊將樹變為兩個連通塊，第二棵樹上必然有一條在這兩個連通塊之間的邊。直接做是 \(O(n^2)\) 的。上個 LCT 容易通過。

當然有不用 LCT 的做法。你考慮兩棵樹都以 \(1\) 為根，對于第一棵樹上每個點，若其與父親的邊第二棵樹上不存在，就斷開這條邊加入這個點與第二棵樹上的父親的邊。但有個問題是第二棵樹上這個點的父親有可能目前是這個點的兒子。為了避免這種情況，倒著從葉子往上刪。每次刪去一個葉子和其父親的連邊，加入其在第二棵樹上父親的邊，然后在第二棵樹上將這個點與其父親合并。正確性不難說明。復雜度是 \(O(n \log n)\) 的。

80 P13526

\(O(n^2)\) DP 是簡單的。

由于第二維是和子樹深度有關，自然思考能否直接使用長剖。直接做有一個問題是，添加 \(u\) 和父親的邊權 \(w_u\) 時，轉移形如 \(f_{i+1} \gets f_i+w_u\)，這個并不是很容易直接做。如果有凸性就有說法了，于是猜一手其就是凸的。

猜出來了就做完了。合并是形如 \(a_i+b_j\rightarrow c_{\max(i,j)}\)，要求 \(i+j \leq k\)。不妨假設現在合并 \(a_{0,\cdots,n}\) 與 \(b_{0,\cdots,m}\) 且 \(n\leq m\)，把 \(b\) 前后 \(m\) 個數拉出來暴力求值，中間的變化量是一樣的。用multiset 即可直接維護差分，根據長剖理論，復雜度是 \(O(n \log n)\) 的。

凸性的證明應該是對 DP 數組歸納。

81 P13531

一年前做過，現在看來，這個題還是很有趣的。

自然的思路是建出 ACAM 后每個點對應一條到根鏈，但是這個結構并不容易進行刻畫，原因是詢問有 \(l,r\) 兩個限制，并且每個點對應一條鏈的結構還是太難直接做了。

一個常見的轉化方式是，嘗試將區間查詢改成前后綴形式。比如說記 \(s_i\) 表示 \([1,i]\) 答案。則 \(s_r - s_{l-1}\) 再減去所有 \(a < l, b \in [l,r]\) 的區間 \([a,b]\) 即為答案。

找到滿足 \(a<l\) 且 \(b\in [l,r]\) 中 \(b\) 最大的，則右端點在 \([b+1,r]\) 內的區間答案就是 \(h_r-h_b\)。對于右端點在 \([l,b]\) 的，其相當于詢問 \(s\) 中一個給定串的一個后綴中有多少子串符合條件。倒著建 ACAM 就行。最后這一步相當巧妙，其本質是嘗試將任何一個詢問放到現有的給定的串上做詢問，從而降低本質不同詢問的數量。

82 NFLS 模擬賽 T1

枚舉 LCP 就行。

83 NFLS 模擬賽 T2

這個題感覺有點難啊，不懂為什么過了這么多。

整個選的區間形態是一開始有個 \([l,r]\)，然后每次選一個 \([a,b]\) 使得 \(a \leq r+1\) 且 \(b \geq r+1\)。

嘗試對這個過程做 DP。對于一個方案我們會選定一個打通區間的子段 \([x,y]\)，獲得 \(\sum \limits_{i=1}^x a_i + \sum \limits_{i=x}^y b_i + \sum \limits_{i=y}^n c_i\) 的收益。考慮上述選的區間為 \([l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]\)，則 \(y \in [r_{k-1},r_k]\)。我們對前 \(k-1\) 個區間做 DP，枚舉最后一個區間，就容易算出答案。

有一個問題是 \(k=1\)，這個時候相當于要對于每個區間 \([l,r]\) 計算 \([x,y] \subseteq [l,r]\) 的答案。這個掃描線一下就行，不太難。

84 NFLS 模擬賽 T3

點分治優化建圖板子。

85 NFLS 模擬賽 T4

目標是求補圖的 MST。

考慮補圖每條邊 \((u,v)\) 邊權是重構樹樹上 LCA 點權。按照 Kruskal 的過程按照權值小到大加入，那么相當于 Kruskal 重構樹上從下往上做。我們直接維護每個子樹合并后得到的若干個連通塊，那么每次就是嘗試把左子樹和右子樹連通塊合并。事實上你直接暴力枚舉較小子樹連通塊內每個點，枚舉右子樹連通塊，然后直接暴力做合并。這個的復雜度是可以分析到 \(O(n \log n)\) 的，如果你能精細實現到不用 \(\log\) 數據結構做合并那就是一個 \(\log\) 的，多一個 \(\log\) 也可以通過。

復雜度分析是你考慮當且僅當一條邊在原圖存在且被枚舉到才會導致復雜度爆。這個東西分析一下可知確實是對的。

86 P11994

值域小肯定是有意義的，不妨考慮從值域上入手。

對于每個 \(x\)，找到所有 \(a_i=x\) 的位置，選為負數的是一段后綴。且不難注意到隨著 \(x\) 增大，如果有一個 \(x\) 被選，則其后面比 \(x\) 小的數也被選了，不然你可以把這個數刪掉替換成后面那個小于 \(x\) 的數。

這引發了一個貪心策略，從小到大依次枚舉 \(x\)，選擇能選的盡量長的后綴。正確性是考慮調整法。

考慮怎么維護這個貪心過程。在外層枚舉 \(x\)，對于每個詢問嘗試二分出最長選的后綴。判定時，由于其之后小于 \(x\) 的數一定會被選擇，所以從被選位置開始的一段最小前綴和是不難預處理出來并做區間 RMQ 的。而詢問左端點到被選位置的和也不難算出。復雜度 \(O((n+q)V\log n)\)。

87 P13345

這個題是有點說法的。

首先最終順序已知，不加思考地直接從前往后記 DP 的話怎么說都只能做到 \(O(nm^2k)\)。一個瓶頸是你要對每個人做一個值域為 \(O(mk)\) 的背包，徹底倒閉了。

不妨假設所有人分數兩兩不同，然后考察什么情況下能得到目標排列。

顯然每個人刪去一些得分后，我們得到了其的一個得分區間 \([l_i,r_i]\)，限制基本上就是要求兩兩無交，有時可以在端點相交，取決于編號順序。

這里有一個很厲害的觀察，你發現整個數軸長度為 \(mk\)，每蓋掉一個位置，對應那個人區間長度增加 \(k\)。相當于是說你最多蓋掉 \(m\) 個位置，不然肯定有相交。

然后考慮從前往后 DP。\(f_{i,j}\) 表示考慮到第 \(i\) 小的得分，之前蓋掉 \(j\) 個數，\(r_i\) 的最小值是多少。轉移枚舉 \(i+1\) 蓋掉多少個位置，預處理 \(i+1\) 這個人選 \(i\) 個位置和為 \(j\) 是否可行。這個地方看起來也要做 \(n\) 次 \(O(mk)\) 的背包，但顯然要求 \(j\) 不超過 \(i,i+1\) 得分差。而總得分差是 \(O(mk)\) 的，所以復雜度其實是 \(O(m^3k)\) 的。

這樣的話背包部分是 \(O(m^3k)\)。外層 DP 轉移先枚舉前 \(i\) 個刪了多少再枚舉 \(i+1\) 選的個數那就是 \(O(nm^2)\) 了。

我們其實可以做到更優。注意到外層 DP 瓶頸是你不僅要枚舉 \(i,j\)，還要枚舉下一個人的狀態。干脆只枚舉下一個人的狀態，也就是枚舉下一個人的左端點和選的數量。所有人的總枚舉量是 \(O(m^2k)\) 的，而對 \(i\) 這個人你只需要雙指針掃過去就行。總復雜度 \(O(nm+m^3k)\)。

說到底這個題精髓還是在于把分數投影到數軸上，得出 \(\sum s_i-s_{i-1} = O(mk)\) 的限制，從而將背包的狀態數減小到與 \(n\) 無關。

88 P12639

這個題的想法相對自然，由于你要對所有點進行排列，而你關心相對順序，一個比較自然的 DP 是 \(f_{i,j}\) 表示 \(i\) 子樹內，點 \(i\) 的排名為 \(j\) 的方案數。轉移合并子樹時，枚舉一側有多少個點在之前的根之前，后面的在根之后。記錄一下前后綴和就可以做到 \(O(n^2)\)。

當然也有一些別的做法。由于這個過程看起來像樹的拓撲序，難點是有兩種邊，所以考慮對某類邊容斥變成只有另一類邊的森林拓撲序計數，同樣可以 DP 的時候進行容斥。復雜度同樣也是 \(O(n^2)\)。

89 P12765

去年 NFLS 模擬賽的題怎么又出現了。

我當時寫的做法是，聲稱若存在長度為 \(x\) 的區間，則必存在 \(x-1,x-2,\cdots,x-6\) 中某種長度也出現過。我已經不會證明了，或者是當時也沒證明過。不過這個題目的性質其實遠比這個強。

題解區有一個高妙的做法。我們考慮三個前綴和序列 \(a_i,b_i,c_i\)，求 \(r-l\) 最大的 \(l,r\) 使得 \(a_r - a_l \neq b_r - b_l, a_r - a_l \leq c_r - c_l, b_r - b_l \neq c_r - c_l\)。令 \(x_i = a_i - b_i, y_i = a_i - c_i, z_i = b_i - c_i\)。則要求 \(x_l \neq x_r, y_l \neq y_r, z_l \neq z_r\)。

如果只有兩維怎么做。每個點 \((x,y)\) 相當于占領了一條橫線和豎線。按照 \(r\) 掃描線，維護可能有意義的所有點。對于任意一個點，與其 \(x\) 坐標相同的點最多一個。所以本質上只有 \(O(1)\) 個有用的點。三維是類似的。

90 P14231

經典套路，對相鄰兩個數和小于等于 \(k\) 進行刻畫，可以將小于等于 \(\lfloor \dfrac{k}{2} \rfloor\) 的視作 \(0\)，大于 \(\lfloor \dfrac{k}{2} \rfloor\) 視作 \(1\)，則相鄰 \(0\) 可以隨便選，相鄰 \(1\) 不能同時選，\(0,1\) 相鄰則有限制。顯然會取所有 \(0\)，以及符合條件的 \(1\)。

按 \(k\) 掃描線可以求出若干貢獻，查詢 \([l,r]\) 形式是 \([l',r'] \subseteq [l,r]\) 求和。整體二分是 \(O(n \log^2 n)\) 的。好像還能 \(1\) 個 \(\log\)，我不會。

91 ARC186D

考慮雙射轉化。一個合法序列可以雙射成一棵 \(n\) 個點的有根樹，\(a_i\) 表示 DFS 序第 \(i\) 個點的兒子個數。

故序列 \(a\) 合法當且僅當：

1. \(\sum \limits_{i=1}^n a_i = n - 1\)
2. \(\forall 1 \leq i < n, \sum \limits_{j=1}^i a_j \geq i\)

同時成立。

枚舉 LCP，枚舉 LCP 下一位選的數是 \(x<a_{i+1}\)，不難將序列計數轉化為格路計數，形式是反射容斥的形式。注意到 LCP 為 \(i\) 則要求 \(\sum \limits_{j=1}^i a_j < n\)，故總復雜度 \(O(n)\)。

92 QOJ7649

\(m\) 很大，但顯然我們只關心元素相對順序。記 \(f_{i,j}\) 表示長度為 \(i\) 值域為 \(j\) 的序列個數，\(g_{i,j}\) 表示長度為 \(i\)，每個數范圍 \([1,j]\)，且 \([1,j]\) 每個數都出現過的序列個數。\(g\) 不難由 \(f\) 二項式反演在 \(O(n^3)\) 復雜度內得到，問題難點變為求 \(f\)。

考察序列的前綴最大值，不難發現前綴最大值把整個序列分段后，每一段的值域確定。對于 \(f\) 的轉移，考慮枚舉最后一個前綴最大值位置即可。復雜度 \(O(n^4)\)。

詢問時，枚舉序列本質不同數的個數即可。總復雜度 \(O(n^4+qn)\)。

93 CF1276F

基于 \(\texttt{*}\) 在子串中的位置進行分類，只有形如 \(s+\texttt{*}+t\) 的形態是相對困難的。

對于這個問題，考慮在 SAM 上枚舉 \(s\)，考察可行的 \(t\)。注意到對于 \(\mathrm{Endpos}\) 相同的 \(s\)，其可能的 \(t\) 也相同。事實上，令 \(S\) 為 \(s\) 的 \(\mathrm{Endpos}\) 集合，則 \(t\) 應該是原串所有 \([i+2,n]\) 后綴的所有前綴的并，其中 \(i \in S\)。原因是由于 \(\texttt{*}\) 在 \(s\) 后，所以 \(i+1\) 就被改成了 \(\texttt{*}\)，\(t\) 就是從 \(i+2\) 開始的一段前綴。

嘗試考察一個集合 \(T\) 的所有 \(i \in T\) 的 \([i,n]\) 的前綴并大小。這顯然等于將他們按照字典序排序后總長減去相鄰兩項 LCP。求出后綴樹組后在 SAM 上線段樹合并維護即可，復雜度 \(O(n \log n)\)。

94 NFLS 模擬賽 T1

這個結構是有向基環樹，但顯然 \((x,y)\) 和 \((y,x)\) 是一樣的，所以你不關心邊的方向。\(x,y\) 合法充要條件是加邊后圖依然是基環樹森林。并查集維護即可。

95 NFLS 模擬賽 T2

為啥模擬賽有計算幾何啊，吐了。

做法就是，你把每條給定直線按照在詢問直線上的交點橫坐標排序，只需要考慮相鄰兩條直線，調整法不難證明。

96 NFLS 模擬賽 T3

離線掃描線，每個點 \(i\) 維護其對應左邊最小的位置。KDT 做即可。KDT 常數太大過不去，不過復雜度是對的。

97 NFLS 模擬賽 T4 / 洛谷 P9997

首先詢問的時候把跨過 LCA 的單獨計算。現在變為祖先鏈查詢。

然后大概就是說你做樹剖，跨過重鏈的不難計算，重鏈內部的每次修改時對里面 \(O(x)\) 個位置重構，算一下哈希值放哈希表里應該就對了。

98 ARC188D

這個題場上為啥過這么少啊。

首先他告訴你了 \(a\) 的排名，所以不妨令第 \(i\) 個序列第一個數就是 \(i\)，要求 \(a_i \in [2i-1,2i]\)。令 \(c_i = a_i \bmod 2\)。

當 \(c_i=0\) 時，說明最后一個數為 \(i\) 的那個序列的反串比這個序列小，即那個序列的第二個位置比 \(i\) 的第二個位置小。反之，\(c_i=1\) 說明那個的第二個比這個大。

所以對于 \(b\) 確定后，每個編號 \(i\) 會和編號 \(x_{i,3}\) 的序列產生限制，要求第二個數比其小或大。\(b\) 合法當且僅當連邊后不會構成環。

由于 \(x_{i,3}\) 是排列，所以將有向邊看作無向邊后，整個圖由若干環構成。而原限制在有向圖上。一個無向環在有向圖上也是環當且僅當環上所有 \(c\) 同色。

即求有多少方案使得不存在同色環。

對于原始給定的若干 \(b_i\)，我們直接連邊 \((i,b_i)\)，每個連通塊現在是環或鏈。進一步，環必須要是非同色，否則答案為 \(0\)。環沒有任何意義，將環都刪掉。然后每條鏈可能是全白，全黑或雙色。這些鏈顯然等價于一個點。對同色環做容斥，欽定 \(c\) 個環同色，容斥系數 \((-1)^c\)，然后環外的點若有 \(k\) 個則方案數是 \(k!\)，故我們只關心被欽定成環上的點的個數。對黑白分別 DP 后類似卷積合并即可。DP 類似第一類斯特林數，\(f_{i,j}\) 表示前 \(i\) 個點做容斥，有 \(j\) 個點在環上的所有結果和。轉移直接考慮插入進某個環或產生新環或不欽定其在環上。復雜度 \(O(n^2)\)。

99 P13078

一棵樹是 MST 當且僅當每條非樹邊大于樹上相應路徑的任意一條邊。

從前往后貪心，確定非樹邊答案時優先把對應路徑上所有邊確定答案，樹上并查集維護即可。

100 P12573

這個題很容易嗎。

\(q=1\) 時，建出 Trie，相當于從根開始每次往任意一個兒子走，如果兩個兒子有一側為空則可以獲得 \(2^i\) 的收益。最大化收益和。直接 DP 即可。

反過來，這等價于從任意一個葉子節點出發到根，對于每個點若其沒有兄弟則獲得 \(2^i\) 的收益。問最大收益。

先對全局建 Trie，對于每個 \(i\) 來說，考慮其被的所有祖先什么時候會產生貢獻。對于其兄弟子樹求出前驅后繼分別為 \(x,y\)，則只有 \([l,r] \subseteq (x,y)\) 時這個子樹會為空。

這 \(m\) 個 \((x,y)\) 會產生 \(O(m^2)\) 個本質不同區間，現在形如有 \(O(nm^2)\) 個區間 \([x_i,y_i]\) 和權值 \(v_i\)，\(q\) 次查詢給定 \(l,r\)，求 \(\max \limits_{[l,r]\subseteq [x_i,y_i]} v_i\)。掃描線將問題轉化為 \(O(q)\) 次區間查詢最大值，\(O(nm^2)\) 次單點修改。可以分塊平衡之，復雜度 \(O(q\sqrt n+nm^2)\)。

101 煉石 NOIP R15T1

難點在于想到二分，然后直接貪心就行了。

怎么想到二分呢，我覺得有點難。

102 煉石 NOIP R15T2

我覺得這個題就是很難，怎么會過這么多。

把偶數位字符反轉，則操作就是選定 \(i\)，然后 \(x_i \gets x_{i+1}\)。

所以整個序列相對來說變得越來越穩定。對于任意一個后綴 \([i,n]\)，\(x\) 中 \([1,i]\) 連續段數必然要大于等于 \(y\) 中對應連續段數，否則不可能成功操作。此外，要求 \(x_n=y_n\)。

這確實是充要條件，線段樹維護即可。

感覺這個題難點是為什么會想到偶數位反轉，這個東西還是很巧妙的。這個題并不僅有這個東西是不變量，你把序列做異或差分也能得到一個不變量，但那個結論并不能推出充分性。這個過程感覺很奇怪。

103 煉石 NOIP R15T4

這不是我們 P12768 嗎。

套用這個題做法就行。但其實也可以不用，這個題沒卡空間，優化建圖直接就能過。

104 NFLS 模擬賽 T1

二分答案 \(k\) 后，找到任意一個子樹深度恰為 \(k\) 的點，則必選中這個點。對剩下的部分做換根 DP 即可。

105 NFLS 模擬賽 T2

注意到你不需要記乘積 \(s\) 而只需要記 \(\lfloor \dfrac{n}{s} \rfloor\)，所以復雜度是 \(O(rc\sqrt{n})\) 的。

106 NFLS 模擬賽 T3

有結論：若一個 \(k\times k\) 正方形為拉丁方，則對于任意 \(i > \dfrac{n}{2}\)，其左上角的 \(i \times i\) 矩形不是拉丁方。

首先考慮如何判定一個正方形是否合法。每個點處理向下和向右最遠位置使得沒有重復數字，而恰有 \(k \times k\) 個只需要做個集合哈希即可。現在我們可以 \(O(1)\) 判定一個矩形是否合法。

對于原問題，枚舉正方形左上角 \((i,j)\)，考慮閾值 \(B\)。對于 \(k \leq 2B\) 的，直接枚舉并判定。對于 \(k > 2B\)，每個 \([xB,(x+1)B)\) 中至多一個 \(k\) 合法。且注意到若 \(k=cB+l\) 合法，則這個 \(k\times k\) 矩形內所有數的集合與 \(x \in [i,i+cB-1],y \in [j,j+B-1]\) 的長方形數的集合相等。這本質上就是之前結論的進一步推廣。所以只需要判定 \(O(n^{2.5})\) 個矩形即可。復雜度 \(O(n^{2.5})\)。

107 P13757

\(\geq\) 是好做的，考慮減去存在 \(x\in S,y\notin S, a_x=a_y\) 的情況。

顯然若存在，則 \(S\) 內有且僅有一個非空集合 \(P\)，\(S\) 外有且僅有一個集合 \(Q\)，滿足 \(P\cup Q\) 內任意兩個序列相等。對此考慮容斥。

枚舉欽定 \(|P|=x,|Q|=y\)，容斥系數 \((-1)^{x+y}\)，每個位置貢獻是一樣的，所以答案是 \(g^m\)，\(g\) 是每一個數有多少種方案。\(g=\sum \limits_{i=1}^v i^{x}(v-i+1)^{n-k-y}\)。

問題變為快速對于所有 \(x,y\) 計算 \(\sum \limits_{i=1}^v i^{x}(v-i)^y\)。

考慮遞推。邊界 \(x=0\) 或 \(y=0\) 是自然數冪求和，拉格朗日插值即可。當 \(x,y > 0\) 時。注意到 \(i^{x}(v-i)^y=i^x(v-i)^{y-1}(v-i)=vi^x(v-i)^{y-1}-i^{x+1}(v-i)^{y-1}\)，對此遞推即可，復雜度 \(O(n^2 \log m)\)，瓶頸在于快速冪。

108 P14256

形式化地考慮數分別是 \(0,1,2\)，\(0\) 擊敗 \(1\)，\(1\) 擊敗 \(2\)，\(2\) 擊敗 \(0\)。

首先相鄰兩個相等一開始就能操作，現在考慮相鄰兩項不同。

考慮原序列模 \(3\) 意義下的差分 \(s_i = (a_i - a_{i-1}) \bmod 3\)。則不難看出操作等價于:

1. 選擇相鄰兩個 \(1\)，將其變為一個 \(2\)。
2. 選擇相鄰兩個 \(2\)，將其變為一個 \(1\)。
3. 選擇相鄰的 \(1,2\)，將其刪去并獲得 \(1\) 的收益。

據此引出一個從前往后貪心的算法。由于只有 \(1,2\) 能產生貢獻，所以沒有匹配的 \(2\) 必然要兩兩合并，剩下 \(0\) 個或 \(1\) 個。所以總是形如 \(21\cdots 1\) 或 \(1 \cdots 1\)，記錄 \(1\) 和 \(2\) 的個數即可貪心。

對于原問題，將 \(1,2\) 個數以及目前末尾數是什么加入狀態中即可。復雜度 \(O(n^2)\)。

109 QOJ14573

直觀的想法是詢問一些特殊圖。詢問鏈可以獲得 \(\sum a\)，詢問以 \(i\) 為中心的菊花可以獲得 \(a_i\) 加上除了 \(i\) 的最大兩個數。

詢問上述信息，共 \(n+1\) 次。令 \(b_i\) 為 \(a\) 排序后第 \(i\) 大，則通過分析每個 \(i\) 在詢問中的貢獻不難得到 \(b_1+b_2\)，據此可以確定每個點的點權。但題目要求你必須找到不能確定的位置，也就是你要找到 \(a\) 最大的兩個位置。

記 \(f(i)\) 表示詢問以 \(i\) 為中心的菊花返回的結果。考慮所有使 \(f(i)\) 取到最大值的 \(i\)，則 \(a_i\) 的取值必然是 \(b_1,b_2,b_3\) 之一。令 \(S\) 為 \(f(i)\) 取到最大值的 \(i\)，我們的目標是在其中找到兩個特殊點，使得其分別對應 \(b_1\) 和 \(b_2\)，而 \(S\) 中其他數都是 \(b_3\)。

首先根據之前的詢問，\(b_3\) 是確定的。令 \(T = \overline{S}\)，不妨設 \(|T| \geq 3\)，此時存在一種二類詢問能做到給定 \(A,B,C\)，判定兩個特殊點是否恰好分別屬于 \(A,C\)。我們把 \(T\) 的點拉成一條鏈，把 \(A\) 和 \(C\) 掛在鏈左右兩側，把 \(B\) 掛在中間。則當且僅當直徑長度為 \(\sum a_i - b_3\times c\) 時兩個點分別處于兩側，\(c\) 是對應的那個數量，算一下就行。這是因為如果在同側或有一個在 \(B\) 中則直徑必然不可能有這么長。

枚舉二進制位嘗試區分兩個特殊點。枚舉到某位后得到兩個集合 \(A,B\) 將特殊點劃分開來，對于 \(A,B\) 分別再枚舉對應二進制位嘗試找到特殊點即可。次數在 \(2 \log_2 n\) 以內。

\(|T|<3\) 時，依次枚舉 \(S\) 中每個數，判定其是不是特殊點，不是則加入 \(T\)，直到找到兩個特殊點或 \(|T| \geq 3\)。

110 P11988

每次定向后如果得到的不是 DAG，則大小大于 \(1\) 的 SCC 對你來說肯定是不優的，這樣你得到的信息很少。

所以不妨考慮將限制強化成每次都定向為 DAG。

如果找到了一種定向能從 \(s\) 到達 \(t\)，則將 DAG 的拓撲序拉出來，我們可以通過一次詢問判定 \(s,t\) 的拓撲序屬于 \([l,r]\) 是否成立，方法是只保留兩端都處于 \([l,r]\) 內的邊，將其他邊反轉。據此我們可以在 \(2 \log_2 n\) 次詢問內得到 \(s,t\)。

對于原問題，難點變為找到一個定向使得 \(s\) 能到 \(t\)。顯然圖越稀疏越難做，考慮樹怎么做。一個想法是點分治，每次找出重心后，枚舉二進制位將所有兒子劃分進兩個集合，這樣每個重心詢問次數是 \(O(\log n)\)，總次數 \(O(\log^2 n)\)，考慮選重心后，從小到大加入鄰居子樹使得兩個集合都在 \([\dfrac{1}{3},\dfrac{2}{3}]\) 之間，這顯然能構造出來。這個做法和三度化后邊分治是類似的。次數大概是 \(2(\log_2 n + \log_{1.5} n)\)。肉眼可見的卡不滿。

對于圖的問題，隨便找一個生成樹。定向時，將樹定向的結果拓撲排序，然后非樹邊從小往大連即可。

111 煉石 NOIP R16T1

猜測貪心做法是每次刪掉最靠后的符合條件的位置，實則確實如此。復雜度線性。

112 煉石 NOIP R16T2

同余最短路轉圈技巧普及題。這里描述一下這個過程。

一般同余最短路問題中，我們令 \(m\) 為選取的模數，此題中有 \(m=a_1\)。將每個數 \(x\) 寫為 \(x=km+b\)，觀察到若 \(x\) 被表示，則 \(x+m\) 也可以。記 \(f_i\) 表示 \(b=i\) 時最小的能被表示的 \(x\)，構造圖 \(i \xrightarrow{a_j} (i+a_j) \bmod m\)，\(f_i\) 即為最短路。

按照一般最短路的求法，我們只能做到 \(O(nm \log m)\) 求解整個圖，而本題我們希望 \(O(nm)\) 求解每個前綴答案。這時引入轉圈技巧。我們考慮加入每個 \(a_j\) 時，會加入所有 \(i \xrightarrow{a_j} (i+a_j) \bmod m\) 的邊，構成了 \(\gcd(a_j,m)\) 個環。不難注意到每個環上最短路不可能經過多次同一個點，所以對這個環松弛兩遍就可以得到答案。復雜度 \(O(nm)\)。

113 煉石 NOIP R16T3

每個區間答案肯定形如一些 \(\texttt{A}\)，一些 \(\texttt{B}\)，……，一些 \(\texttt{Z}\)，加上一個原串的區間。這不難通過枚舉 \(\Sigma\) 中的所有字符在 \(O((n+q)|\Sigma|\log n)\) 的復雜度內求出，然后哈希或者后綴數組就可以比較兩個的字典序。

\(O(n|\Sigma|\log n)\) 太大了，可以優化到 \(O(n|\Sigma|+q|\Sigma|\log n)\)，足以通過。

114 煉石 NOIP R16T4

首先 SG 值大概是 \(f_u = \mathop{\mathrm{MEX}} \limits_{j \in \mathrm{subtree}_u} \{f_j \oplus ((d_j-d_u-1)\bmod 2)\}\)。

考慮這個結構，我們首先觀察到，\(\lfloor \dfrac{f_u}{2} \rfloor\) 從葉子到根單調不降。其次，每個點的 \(f_u\) 只和兒子的最大值和嚴格次大值有關。若最大值和嚴格次大值分別是 \(2k+1\) 和 \(2k\)，則 \(f_u=2k+2\)，否則 \(f_u\) 為最大值異或 \(1\)，原因稍微分析一下就行。

注意到 \(f_u\) 的量級是 \(O(\log n)\) 的，所以事實上一條鏈上兒子最大次大分別是 \(2k\) 和 \(2k+1\) 的點數也只有 \(O(\log n)\)，對此使用數據結構維護一些信息就能查詢了。直接樹上倍增可能是有前途的，樹剖也很有前途，我也沒研究明白細節。

115 P14230

首先大家都會貪心匹配子序列。

整個過程分為兩部分，分別是內層子序列和外層子序列。對內層子序列 DP，\(f_i\) 表示內外層貪心都選到 \(i\) 的答案。轉移枚舉下一次內層轉移到 \(j\)，計算 \(i\) 到 \(j\) 有多少本質不同子序列在到 \(j\) 前沒有選過等于 \(a_j\) 的數，記作 \(g_{i,j}\)，那么有 \(f_i \times g_{i,j} \rightarrow f_j\)。只要能快速算 \(g\) 就能求解原問題。

對于 \(g\)，考慮先算 \(h_{i,j}\) 表示從 \(i\) 到 \(j\) 但沒有 \((i,j)\) 間不選等于 \(a_j\) 的限制的方案數。這個容易 \(O(n^2)\) 計算。則 \(g_{i,j}\) 可以通過枚舉最后一次選等于 \(a_j\) 的位置 \(k\) 并減去 \(h_{i,k} \times g_{k,j}\) 計算而來。復雜度 \(O(n^3)\)。

這個求 \(g\) 的做法前途不太好，考慮不要顯式計算 \(g\)，而是把貢獻過程直接刻畫在 \(f\) 轉移中。從 \(i\) 到 \(j\) 相當于要求不經過 \(=a_j\) 的數。記 \(w_{i,j}\) 表示目前結尾為 \(i\)，要求不經過等于 \(j\) 的總權值和。對相同的 \(j\) 記錄 \(w_{i,j}\) 的前綴和即可在 \(O(n^2)\) 內解決整個問題。空間也是 \(O(n^2)\) 的，但已足以通過。

116 NFLS 模擬賽 T1

每種顏色單獨做，按照 \((x,y)\) 二元組遞增順序考慮，樹狀數組做一下即可。復雜度 \(O(n^2 \log n)\)。

117 NFLS 模擬賽 T2

有一些基于直接維護等差數列連續段的做法，每個連續段被完全覆蓋則個數會減半，據此可得一個 \(O(n\log^2m)\) 的做法，太蠢了。

注意到我們可以快速計算操作 \([l,r]\) 后第 \(x\) 個位置在這次操作前是第幾個位置。具體來說，分類討論 \(x\) 之前是 \([1,l),[l,r],(r,n]\) 中哪一部分即可。

倒著做，每次向平衡樹中插入詢問的值，然后按照操作區間對平衡樹做分裂并支持維護乘法和加法，分裂后合并回去即可。

時間復雜度 \(O(n \log n)\)，空間線性。

這個做法其實類似于插入標記回收的那套做法，不過你不需要做有交合并，因為你把區間分裂出來后操作仍然是三部分有序的而不會值域有交。

118 NFLS 模擬賽 T3

注意到每個左端點至多對應一個右端點，只需要二分出來即可，問題變為 \(O(n \log n)\) 次查詢子串排名。

先做后綴數組，則詢問的是后綴樹上一段到根鏈的排名。找到這條到根鏈向下的最靠左的鏈，變為查這條鏈右側點數，直接做即可。復雜度 \(O(n\log^2 n)\)。

119 NFLS 模擬賽 T4 / QOJ5175

考慮到這些最短路的并就是最短路樹，這個結構類似于斯坦納樹，考慮狀壓 DP。

\(f_{i,j,S}\) 表示 \(i\) 子樹內，進行了 \(j\) 次操作，已經選定了 \(S\) 這個特殊點集合的情況下的答案。轉移分為往父親接，或者在同一個 \(i\) 處合并 \(S,T\) 變為 \(S \cup T\)。

直接做復雜度 \(O(nm^23^k)\)，瓶頸在于合并 \(S,T\)。但不難注意到 \(f_{i,j,S}\) 在 \(S\) 固定時，隨著 \(j\) 單調遞增，\(f\) 值單調不增。而合并是取 \(\max\)，所以不難做到 \(O(nm3^k)\)。

120 P11983

這是好題啊！

對于字典序問題，一個想法是逐位貪心，但對于一個區間確定了最大值后，你不容易確定最大值在哪，所以不是很有前途。

考慮另一種思路，從大到小枚舉最大值，從前往后枚舉區間使得盡量多的區間的最大值為枚舉的數。

具體來說，我們枚舉每一個數 \(i\)，記其出現了 \(c\) 次，然后從前往后掃描每個區間，并維護目前哪些區間最大值會被選為 \(i\)。每次加入一個區間，要求這個新的集合的最小點覆蓋不超過 \(c\)。不難發現不同的 \(i\) 之間不會互相影響，因為如果最小點覆蓋的位置之前被其他某個 \(j>i\) 選了，那這個區間上一次也應該被選。至此我們已經得到了一個多項式復雜度算法。

假設最終確定了 \(k\) 個區間最大值為 \(i\)，我們希望復雜度和 \(n\) 無關而和 \(k\) 有關，這樣總復雜度就對了。

首先可以發現，只要最小點覆蓋 \(<c\)，則每次加入區間都必定成功，因為最小點覆蓋至多增加 \(1\)。而當最小點覆蓋恰好等于 \(c\) 后，之后加入的區間要滿足加入后最小點覆蓋不變。故整個選的過程是一段前綴和后面若干個散點。

對于前綴，直接的想法是二分。不過為了復雜度和 \(n\) 無關，考慮倍增二分。即從小到大每次嘗試將目前前綴長度乘以 \(2\) 并做判定，這樣我們判定的前綴長度不會超過答案前綴長度兩倍。這部分的復雜度是 \(O(k \log^2 k)\) 的。

現在考慮之后加入的散點怎么做。為了研究清楚這個事情，你肯定要研究清楚對于一個集合 \(S\)，加入什么區間 \([l,r]\) 會使得最小點覆蓋不增加。不妨考慮原最小點覆蓋大小為 \(k\)，則相當于會有一個點序列 \(x_1,x_2,\cdots,x_k\)，不難注意到每個 \(x_i\) 存在一個上下界 \([l_i,r_i]\)，感性理解不難看出這些區間互不相交。這個 \([l_i,r_i]\) 是不難通過正反做兩次貪心得到的。而加入一個區間 \([L,R]\) 可行當且僅當 \([L,R]\) 與某個 \([l_i,r_i]\) 有交。

考慮加入一個 \([L,R]\) 后 \([l_i,r_i]\) 怎么變化。將 \([L,R]\) 按照與 \([l_i,r_i]\) 的關系分類。具體來說，將所有與某個 \([l_i,r_i]\) 有交的 \([L,R]\) 分類為，包含某個 \([l_i,r_i]\)，恰與一個有交，或恰與兩個有交。

包含某個 \([l_i,r_i]\) 是好的，其不會對任何 \([l_i,r_i]\) 造成影響。

恰與某個相交但不包含任意一個時，相當于 \([l_i,r_i]\) 與 \([L,R]\) 求交。

而與兩個相交，形如 \([l_i,r_i],[l_{i+1},r_{i+1}]\) 均與 \([L,R]\) 有交。你發現其并不會直接影響 \([l_i,r_i]\) 與 \([l_{i+1},r_{i+1}]\)，但如果某次求交后 \(r_i < L\)，則 \(r_{i+1} \gets R\)。同理 \(l_{i+1} > R\) 則 \(l_{i} \gets L\)。

現在我們的目標就是，能通過某個結構維護最靠前的和某個 \([l_i,r_i]\) 有交的區間，那么第一類區間直接忽略，第二類對單個 \([l,r]\) 進行修改，第三類考慮把這個標記掛在 \(i,i+1\) 上，之后進行操作 \(2\) 遞歸執行標記操作。標記的總次數是 \(O(k)\) 的所以是對的。

現在考慮什么結構能求解最小有交編號。你發現第二三類都比較好，只會和一個或兩個 \([l_i,r_i]\) 有影響。第一類比較難受，但由于 \([l_i,r_i]\) 無論如何都在縮小，所以你壓根不需要找最小的 \([L,R]\)，而是找到所有這樣的 \([L,R]\)，那么你只需要在修改 \([l,r]\) 時，把所有包含這個區間的 \([L,R]\) 拉出來就行了。而二三類就很容易用線段樹做了。復雜度是兩個 \(\log\) 的。

121 P11408

考慮樸素的 DP 結構，\(g_u = \max \limits_{j} \{g_j+w_j\}\)，每個點的 \(f(u)\) 為兒子的最大和次大 \(g_j+w_j\) 的和。

對于每個點，稱其實兒子為 \(g_j+w_j\) 最大的。整棵樹被我們做了一個剖分。每個點的 \(f\) 為實兒子 \(g_j+w_j\) 加上虛兒子最大的 \(g_j+w_j\)。

每次修改操作，由于加的是正數，從 \(u\) 開始往根不斷跳，會有若干次切換虛實兒子的過程，直到無法操作為止。我們聲稱這么暴力跳鏈頂并判定這條鏈是否會成為父親的實兒子，直到無法成為停止，\(n,q\) 同階的情況下，總操作次數是 \(O(n \log n)\) 的。原因是我們將每條實鏈染一個顏色，每個點的顏色是所在實鏈的顏色，則操作相當于鏈顏色覆蓋，我們的做法相當于暴力跳到祖先第一個顏色不同的位置，并把這一段染成同顏色。對原樹重鏈剖分，我們的做法不弱于 \(O(\log n)\) 次區間染色，根據顏色段均攤理論即得均攤復雜度 \(O(n \log n)\)。

現在我們只需要維護虛實鏈的更改。相當于是我們要維護一條實鏈整體加一個數，切換某個點的實兒子，查詢某個點的實鏈鏈頂，查詢單點值，維護每個點的虛兒子最大權值。

鏈加單點查可以直接樹狀數組。維護每個點虛兒子可以直接用 multiset。維護實鏈頂可以維護每個點是否為鏈頂，查詢某個點向上第一個是鏈頂的點，樹剖后可以輕松維護。總復雜度 \(O(n \log^2 n)\)。

122 NFLS 模擬賽 T1

點邊容斥，或者也可以視作平面圖歐拉定理，直接做就行。

123 NFLS 模擬賽 T2

顯然只有 \(2^c\) 種本質不同的顏色，這個問題可以先二分答案，然后做二分圖匹配。則 Hall 定理要求答案為 \(k\) 要求 \(\forall S, \dfrac{|N(S)|}{|S|} \geq k\)，則 \(k \leq \dfrac{|N(S)|}{|S|}\)，所以不需要二分答案了。

進一步，怎么求每種顏色是否出現在鏈上。你只需要開個主席樹在樹上暴搜出來就行。復雜度 \(O(n\log n+q4^c+qmc)\)。卡一下常可能可以通過。

124 NFLS 模擬賽 T3

魔怔題。

不可行的相當于是排序后所有長度為 \(l\) 的前后綴和 \([s_1,s_2)\) 構成區間并的結果。

考慮求補集，也就是不包含于 \([s_1,s_2)\) 構成區間內的答案。相當于對某個 \(l\)，最小的 \(l+1\) 個數的和大于最大的 \(l\) 個數和。

你發現這個 \(l\) 其實是 \([1,n]\) 的一個前后綴，證明是顯然的，你二分出來就容易做到 \(O((n+q) \log^2 n)\)。

125 NFLS 模擬賽 T4

先建立 AC 自動機，相當于在自動機上走，要求不能走到某個 Fail 樹到根鏈上有字符串結尾的點。

\(f_{i,s,t}\) 表示，現在在 AC 自動機狀態 \(s\)，并且在末尾加了個 \(i\)，要求走到狀態 \(t\)，問字符串長度最小值。

轉移考慮對 \(b_i\) 從前往后逐個 DP，\(g_{i,j}\) 表示走完了 \(b_1\) 到 \(b_i\)，在 AC 自動機節點 \(j\) 的答案。

注意到結構形如最短路，類似最原始的 bellman-ford，直接做 \(O(G)\) 輪松弛就可以通過。

126 P10430

首先 \(q=1\) 大家都會做，先做操作 A，做完后序列合法當且僅當其單調不降。從后往前做貪心即可。

離線按照左端點掃描線。對于每個右端點維護目前的 \([l,r]\) 里 \(l\) 這個位置要減去多少 \(D\)。顯然隨著 \(r\) 遞增這個值單調不降。維護若干這個值的連續段，每次直接從前往后刪連續段直到操作后 \(l+1\) 的值比 \(l\) 初始值小，這個段之后的變化量是相同的。線段樹維護之，查詢是區間歷史和。復雜度 \(O((n+q)\log n)\)。

127 P10432

好題。

首先，一個點如果增高了，則不可能新增連接設施。

考慮反證。點 \(x\) 增高，目的肯定是連向點 \(y\)，初始 \(h_x \leq h_y\)。如果 \(C_y \leq C_x\)，將所有向 \(x\) 連的都改為向 \(y\) 連，\(x\) 就不用新增連接設施了。如果 \(C_y > C_x\)，初始時 \(x\) 比 \(y\) 小，干脆不要增高 \(x\)，讓 \(y\) 直接連向 \(x\)。如果 \(x\) 用 \(y\) 的是免費的，那就把某個本來指向 \(x\) 現在指向 \(y\)。這樣肯定不劣。

其次，我們聲稱，最終的最小值點一定就是原來的最小值點。原因是如果原來最小值 \(x\) 增高后向 \(y\) 連邊，嘗試改為不增高 \(x\) 然后讓 \(y\) 向 \(x\) 連邊。本來向 \(x\) 連邊可以調整成向 \(y\) 連邊，這樣就不劣了。

據此，考慮按照值域 DP。將每個點海拔增加過程投影到數軸的區間上，\(f_{i,j,k}\) 表示考慮到了 \(i\)，之前還有 \(j\) 個沒用的連接設施，有 \(k\) 個區間跨越 \([i,i+1]\)。增加連接設施時，根據上述結論，不難看出我們直接令增加設施對應花費為初始高度 \(=i\) 的點的 \(C\) 最小值即可。直接做是 \(O(Hn^2)\) 的。優化是說，不難注意到如果某個 \(i\) 不存在 \(H\) 為 \(i\) 的數，其轉移可以直接向后做一個等差數列覆蓋狀物。只對有用的 \(i\) 做 DP，復雜度 \(O(n^3)\)。

128 P10433

好厲害的題。

首先所有人基本獨立，每個除了 \(1\) 的肯定希望走的盡量短。具體來說，其可以第一輪走到某個 \(0\)，然后 \(01\) 交替每輪花費 \(2\)，也可以先走若干輪走到一個 \(0\) 使得其存在一個相鄰的 \(0\)，然后每次都在這兩個 \(0\) 之間走，花費 \(1\)。

前者很容易計算，找到距離每個點最近的 \((0,1)\) 邊即可。另一方面，其有可能走若干輪走到 \((0,0)\) 邊，這個就有點麻煩了。考慮其走到這條邊花了 \(k\) 次，距離為 \(d\)，而整個過程中 \(1\) 號玩家移動了 \(x\) 步。如果 \(x \geq k\)，則這個花費為 \(x-k+d\)。反之，\(x < k\) 時，其只在之前走了若干輪就停下了。我們聲稱也用 \(x-k+d\) 計算并不會讓答案變小，這個是你把路徑畫出來手玩一下就能得到的。

現在每個點 \(i\) 在經歷 \(x\) 輪的權值可以寫作 \(\min(x+a_i,2x+b_i)\) 的形式。至此我們已經得到了一個多項式算法，直接跑分層圖最短路即可。

現在考慮怎么優化這個過程。注意到 \(k\) 較大時，我們不希望輪數太多，因為每增加一輪答案至少增加 \(k-1\)，故如果最少 \(x\) 輪，最多不會超過 \(O(x+\dfrac{n}{k})\) 輪，這樣復雜度就是 \(O(\dfrac{n^2}{k})\) 了。

另一方面，\(k\) 比較小時，注意到每個點的花費是一個形如前面斜率 \(2\) 后面斜率 \(1\) 拼接而成，所有點總共只有 \(O(k)\) 個本質不同段，每段單獨拉出來當作直線算答案，并且你發現斜率前面大后面小是凸的，所以當作直線算答案就是對的。

平衡可得復雜度 \(O(n\sqrt{n\log n})\)。

129 P5479

正常求編輯距離的做法是，\(f_{i,j}\) 表示長度為 \(i,j\) 的前綴編輯距離。直接套用這個做法復雜度是 \(O(n^3)\) 的。

首先考慮對 \(B\) 的每個后綴單獨做，由于 \(k\) 很小，我們希望得到一個關于 \(k\) 的狀態。

現在我們考慮記目前正在處理的 \(B\) 后綴為 \(T\)，原串 \(A\) 為 \(S\)，觀察這樣一個事實：對于固定的 \(j\)，\(S[1,i]\) 與 \(T[1,i+j]\) 的編輯距離大于等于 \(S[1,i-1]\) 與 \(T[1,i+j-1]\) 的編輯距離。這是顯然的。另一方面，顯然兩個編輯距離不超過 \(k\) 的串長度差不超過 \(k\)，故自然的想法是對于每個 \(j\) 和 \(x\)，求出最大的 \(i\) 使得 \(S[1,i]\) 與 \(T[1,i+j]\) 的編輯距離不超過 \(x\)，我們記這個最大的 \(i\) 為 \(f_{j,x}\)。這樣狀態數已經被優化到了 \(O(k^2)\)。

進一步，考慮怎么對 \(f\) 進行轉移。首先是替換，\(f_{j,x} + 1 \rightarrow f_{j,x+1}\)。其二是插入。\(f_{j,x} \rightarrow f_{j+1,x+1}\)。最后是刪除，\(f_{j,x} + 1\rightarrow f_{j-1,x+1}\)。另外，在使用 \(f_{i,j}\) 更新后繼時，先將 \(f_{i,j}\) 加上對應后綴的 LCP，這一步求出后綴數組即可。

復雜度 \(O(n\log n + nk^2)\)。

130 CF1874E

顯然有 DP，\(f_{i,j}\) 表示長度為 \(i\) 返回值為 \(j\) 的排列個數。\(j\) 是 \(O(n^2)\) 級別的。所以直接轉移是 \(O(n^6)\) 的。無法通過。

具體來說，轉移式子是 \(f_{i,j} = \sum \limits_{1\leq x\leq i} \dbinom{i-1}{x-1} \sum \limits_{y+z=i-j} f_{x-1,y} \times f_{i-x,z}\)。

考慮 \(f_{i,j}\) 的 OGF \(F_i(x) = \sum \limits_{j} f_{i,j}x^j\)，則 \(F_i = x^i\sum \limits_{1 \leq y \leq i} \dbinom{i-1}{y-1} F_{y-1}F_{i-y}\)。

由于 \(\deg F_n \leq \dfrac{n(n+1)}{2}\)，直接帶入 \(\dfrac{n(n+1)}{2}+1\) 個點值做拉格朗日插值反推系數即可。復雜度 \(O(n^4)\)。

131 AGC043C

\(10^{18}\) 足夠大，并且 \(i+j+k\) 相等的 \((i,j,k)\) 之間互不影響，所以容易得到多項式復雜度算法，按照 \(i+j+k\) 從大到小貪心即可。

將原圖的邊從小到大定向為 DAG，注意到 \((i,j,k)\) 會選當且僅當其后繼都不選，\((i,j,k)\) 不選當且僅當其存在一個后繼被選。這個結構和博弈完全相同。沒有后繼的點為必敗點，則 \((i,j,k)\) 會選當且僅當其為必敗點。

\((i,j,k)\) 每次只會移動一維，相當于三個游戲，所以考慮三個圖上的 SG 函數，\((i,j,k)\) 必敗當且僅當 \(a_i \oplus b_j \oplus c_k = 0\)。

進一步，考慮 DAG 博弈的 SG 函數，是后繼 SG 函數的 \(\mathrm{MEX}\)。所以 SG 最大值是 \(O(\sqrt m)\) 的。直接枚舉 \(i,j\) 即可，復雜度 \(O(m)\)。

132 煉石 NOIP R17T1

用 set 維護連續段會被卡常。

你倒著做并查集就能過了。復雜度還是 \(O(n \log n)\)。

你可以用線性并查集和線性 RMQ 做到線性。

133 煉石 NOIP R17T2

根號分治直接做就行。

134 煉石 NOIP R17T3

考慮每個數的出現位置 \(l,r\) 可以看作一個區間，所以限制其實是在說，除了 \(i\) 對這個區間與最終區間有交但互不包含，其他區間和最終區間都是要么不交要么包含的。

放在平面上，相當于初始給若干矩形，每次查詢一個矩形內被覆蓋次數恰好為 \(1\) 的點的數量。

從左往右掃描線，維護最小值次小值，做一個歷史版本和即可。一個方便理解歷史版本和做法的方式是考慮線段樹每個點有一個操作序列，每個是 \(+x\) 或者做一次累加歷史和操作。你只需要記錄這個隊列中每次累加之前的加法和的最小值和次小值即可。

復雜度 \(O(n \log n)\)。

135 煉石 NOIP R17T4

好難啊。

136 AGC058D

高妙的題。

ABC，BCA，CAB 共有的特征是下一個數為上一個數加 \(1\)。

考慮對滿足 \(a_{i+1}-a_i \equiv 1 \pmod 3\) 的極長連續段容斥。枚舉 \(i\)，欽定 \(i\) 個連續段。我們只關心連續段開頭的三個字符，所以先把其他的 \(a-i,b-i,c-i\) 個 A，B，C 隨意排列，然后插入 \(i\) 個 ABC，BCA 或 CAB。

由于我們欽定的是極長連續段開頭，所以要求 ABC 前面不能是 C，BCA 前面不能是 A，CAB 前面不能是 B。

那就好做了。你發現對于每個位置，在后面能加的總是 ABC，BCA，CAB 三種之一，所以相當于每個空隙插任意多個總和為 \(i\)，乘以 \(2^i\) 即可。不過你要分討一下在開頭插入，這種是沒有限制的。

復雜度線性。

137 CF1097G

考慮用斯特林數降冪，\(x^k = \sum \limits_{i=0}^k \dbinom{x}{i}i!\begin{Bmatrix} k\\i\end{Bmatrix}\)。

枚舉 \(i\)，則只需要計算 \(\sum \limits_{X} \dbinom{f(X)}{i}\)，組合意義是所有點集的虛樹上選 \(i\) 條邊的方案數。

對此考慮 DP，一個選邊對應的點集個數大概是所有最深被選邊的 \(2^{sz} - 1\) 乘積，以及需要考慮選邊的最淺點外面的部分，然后其他點可選可不選。

對此樹形 DP，\(f_{i,j}\) 表示子樹 \(i\) 選了 \(j\) 條邊對應的答案。復雜度看似是 \(O(nk^2)\) 的，但只要 \(O(\min(sz_1,k)\times \min(sz_2,k))\) 合并子樹復雜度就是 \(O(nk)\) 的。考慮這樣一個事實，在合并兩棵子樹時，不妨看作子樹 A 的 DFS 序后 \(k\) 個點與子樹 B 的 DFS 序前 \(k\) 個點兩兩匹配，顯然任意兩個點最多只會在 LCA 處統計一次，其次會發現對于每個點 \(u\)，會與之匹配的點的 DFS 序和 \(u\) 差是 \(O(k)\) 的，故總復雜度 \(O(nk)\)。

138 CF1842G

考慮組合意義，\((a_i+kv)\) 可以看作每個點向后有 \(a_i\) 種，然后后綴加等價于在這個點放一個工具，之后可以用這個工具向后走，每次走可以有 \(v\) 種方案。然后 DP，\(f_{i,j}\) 表示前 \(i\) 個，用了 \(j\) 個不同工具即可。

139 CF1988F

考慮全局最大值位置 \(x\)，則任意前綴最大值位置 \(y\leq x\)，后綴最大值位置 \(y \geq x\)。所以可以枚舉 \(x\)，分為前后兩部分。

現在相當于只需要考慮前綴最大值和上升數。記 \(f_{i,j,k}\) 表示長度為 \(i\) 的排列有 \(j\) 個前綴最大值和 \(k\) 個上升數的排列個數。考慮從大到小插入數，則新插入的數若想成為前綴最大值只能插在開頭，而若插在后面，插在上升數之間上升數個數不變，否則上升數個數加 \(1\)，現在我們已經可以 \(O(n^3)\) 解決這個 DP。

在中間時，需要合并兩部分。枚舉 \(y, z, u, v\) 表示之前的前綴最大值個數，上升個數，之后的前綴最大值個數，上升個數，貢獻形如 \(f_{x,y,z}g_{n-x,u,v}a_yb_uc_{z+v}\)。直接做是 \(O(n^4)\)，外層枚舉 \(x\) 就是 \(O(n^5)\) 的了。但確定 \(z,v\) 后 \(y,u\) 基本上就是獨立的，不難做到 \(O(n^2)\)，總復雜度 \(O(n^3)\)。

140 CF1210F2

完美匹配考慮 Hall 定理。對于每個沒有完美匹配的圖 \(G\)，考慮欽定一個代表元 \(S\)，使得 \(|S|>|N(S)|\)，我們選取 \(|S|-|N(S)|\) 最大的，在此基礎上選取 \(|S|\) 最小的，我們聲稱其必定唯一，不難反證得到。

考慮 \(f_{S,T}\) 表示左側點集 \(S\) 與右側點集 \(T\) 有完美匹配的概率。我們選取兩個集合 \(S',T'\)，欽定 \(N(S')=T'\) 且 \(S'\) 為代表元。考慮 \(S'\) 為代表元需要滿足什么。首先 \(S',T'\) 內部不存在更優的代表元的可以通過變為子問題解決。其次要求 \(S \setminus S'\) 與 \(T \setminus T'\) 有完美匹配，否則若存在一個 \(X \subseteq S \setminus S'\) 使得 \(|X|>|N(X)|\)，那么令 \(Y=S' \cup X\) 即為一個比其優的代表元。我們聲稱這是充分必要的，原因是考慮若存在一個集合 \(X\) 使得 \(X \cap S' \neq \varnothing\) 且 \(X \cap (S \setminus S') \neq \varnothing\) 且 \(X\) 為更優的代表元，由于 \(S \setminus S'\) 與 \(T \setminus T'\) 有完美匹配，取 \(X \cap S'\) 顯然為更優的代表元。

故枚舉 \(S',T'\) 后只要求 \(S \setminus S'\) 與 \(T \setminus T'\) 有完美匹配，\(N(S')=T'\)，且 \(S',T'\) 這部分中 \(S',T'\) 為代表元。為了處理后面的部分，記 \(g_{S,T}\) 表示 \(S,T\) 部分，\(S,T\) 是代表元的概率，轉移與上述類似。

分析復雜度，枚舉 \(S'\subseteq S\) 與 \(T' \subseteq T\) 的復雜度都是 \(O(3^n)\)，所以總復雜度 \(O(3^{2n})\)。

141 AGC034F

考慮 \(f_i\) 表示答案，\(f_0=0\)，對于 \(i \neq 0\)，有 \(f_i = 1 + \sum \limits_{j} f_{i \oplus j}p_j\)，\(p_j\) 為選 \(j\) 的概率。

也就是，\(f_i = 1+ \sum\limits_{x \oplus y=i} f_xp_y\)。

令 \(\times\) 為集合冪級數的異或卷積，則 \(\forall i \neq 0, f_i = 1 + (f\times p)_i\)。

所以 \(f \times p = (c,f_1-1,f_2-1,\cdots)\)，只要能求出來 \(c\) 即可。

考慮到 \(\sum p = 1\)，所以 \(\sum f_i = \sum (f\times p)_i\)，故 \(c=f_0+2^n-1\)。

考慮 \(p'_i = \begin{cases} p_i && i > 0 \\ p_0 - 1 && i = 0\end{cases}\)。則 \(f \times p' = (2^n-1,-1,-1,\cdots)\)。已知 \(p'\) 和結果故可以求出 \(f\)。而實際上 \(f\) 不一定有唯一解，求出來的不一定滿足 \(f_0=0\)，此時令每個數減去 \(f_0\) 即可。

142 P10435

首先兩個序列 \(A,B\) 匹配肯定是從小到大依次匹配。

二分答案，考慮求出哪些環上區間可行。這不太好做，考慮對于每個 \(i\)，其能匹配的 \(B\) 是一段區間 \([l_i,r_i]\)，則要求環上區間中 \(\leq a_i\) 的數的個數在 \([l_i,r_i]\) 之間。不難注意到對于每個 \(i\) 其能匹配的是一段區間，不難分類討論求出。復雜度 \(O(n \log V)\)。

143 P10440

其實是有點難的。

思路很多，不要局限在某個特定思路中。有一些容易做到 \(3n\) 的做法，比如從 \(1\) 到 \(n\) 依次確定每個點的所有鄰居，但并不是很容易優化。

考慮將樹以 \(1\) 為根，我們的目標是確定每個點的父親。依次詢問 \((1,i)\) 得到距離 \(1\) 第 \(i\) 小的位置 \(u\)，然后嘗試尋找 \(u\) 的父親。依次詢問 \((u,1),(u,2),\cdots\)，每次詢問得到 \(x\) 后，考慮若 \(x\) 在某次詢問 \((1,j)\)，其中 \(j<i\) 中，成為過結果，那么 \(x\) 就是 \(u\) 的父親，否則 \(u\) 是 \(x\) 的父親。

至此，除了詢問 \((1,i)\)，每次詢問都至少得到了一個未確定父親的點的父親，詢問次數不超過 \(2n\)。

144 P10437

靜態 Top Tree 板子題吧。

我還沒寫，加入 todo list。

145 P14311

\(b_x\) 一定是嚴格前綴最大值，\(b_z\) 一定是嚴格后綴最大值，證明顯然。

故三者中至少有一個為全局最大值。若為 \(y\)，容易計算答案。\(x,z\) 對稱，不妨考慮 \(z\) 為全局最大值。

此時顯然有 \(x\) 為嚴格前綴最大值，否則替換為之前的大于等于其的必定不劣。

我們聲稱只需要找到 \(O(\log V)\) 個最大的嚴格前綴最大值做為 \(x\) 計算即可。

原因是你考慮最優的是 \(x,y,z\)，則 \(b_y\) 的限制就是 \(\leq \dfrac{b_x+b_z}{2}\)。此時考慮 \((y,z)\) 之間必然不存在大于等于 \(b_y\) 且小于等于 \(\dfrac{b_x+b_z}{2}\) 的數，所以 \((y,z)\) 之間的嚴格前綴最大值都大于 \(\dfrac{b_x+b_z}{2}\)，且所有大于 \(\dfrac{b_x+b_z}{2}\) 必然單調遞增，因為反之你可以選任意一個逆序對肯定不劣，而這些的任意兩個肯定都不能和 \(z\) 做為三元組，故顯然只有 \(O(\log V)\) 個嚴格前綴最大值。而 \(b_x\) 顯然是 \([1,y)\) 之間的最大值，所以 \((x,y)\) 之間也不會有嚴格前綴最大值。

至此，不難利用一些數據結構在 \(O(n + q\log n\log V)\) 的復雜度內解決問題。

146 P14310

難以注意到，對稱群 \(S_5\) 僅有 \(156\) 個子群。具體來說，搜出來所有子群，發現確實只有這么多。

對每種子群，只保留在群內的邊，判定連通性即可。

147 P10439

不難發現本質就是個貪心，只要 \(l \rightarrow l+1\) 選的是哪個確定，后面的都可以直接貪心得到。

對稱的，只要 \(r-1 \rightarrow r\) 選的是哪個確定，前面的也不難貪心得到。

直接枚舉 \(l,r-1\) 中向下一個點的邊數較小的一側并記憶化，顯然是 \(O(n\sqrt n)\) 的枚舉次數。

加個倍增查詢貪心的結果就是 \(O(n\sqrt n \log n)\) 的。

但是你既然都根號了，寫個分塊平衡復雜度就能做到 \(O(n \sqrt n)\) 了。

148 P14301

一個是非嚴格前綴最大值也是非嚴格后綴最大值的點只可能是全局最大值，故考慮把前綴最大值和后綴最大值分開維護，并對全局最大值特殊處理。

然后就好做了，維護每個點前綴 \(\max\) 減去其自身，每次把新的前后綴 \(\max\) 找出來，操作時特殊處理一下全局最大值即可。

149 煉石 NOIP R18T4 / P8996

先對序列進行一次操作。

我們把所有前綴最大值找出來，發現每個前綴最大值和下一個前綴最大值之間的段是在一起的，操作會在 \(\dfrac{n}{2}\) 的位置把這段分開，然后把后面多出來的這些段歸并到整個序列里面。

不難通過線段樹維護所有前綴最大值與段，復雜度 \(O(q \log n)\)。

150 P14323

定義 \(S_i = \{i \oplus 1, i\oplus 2,\cdots, i \oplus n\}\)。

我們的目標是對于每個 \(j\) 求出 \(p_i \oplus p_j\)，同時我們也得到了 \(S_{p_i}\)。

求出 \(S_{p_i}\) 后，對于每個 \(x \in [1,n]\) 驗證 \(S_x = S_{p_i}\) 是否成立。暴力做是 \(O(n^2)\) 的。

注意到 \(S_x = \{y \mid 1 \leq y \oplus x \leq n\}\)，枚舉 \(y \oplus x\) 與 \(n\) 在二進制下的 LCP，然后可以得到 \(y\) 的一個區間，判定集合相等時做 sum hash，于是預處理哈希前綴和就可以在 \(O(n \log n)\) 的復雜度內判定每個 \(S_x = S_{p_i}\) 是否成立。

不難證明 \(S_x = S_{p_i}\) 的 \(x\) 至多只有兩個，當且僅當 \(n=2^k-2\) 時有 \(S_x = S_{n + 1- x}\)。

所以若 \(n \neq 2^k - 2\)，求出 \(p_i\) 和所有 \(p_i \oplus p_j\) 后排列可以被唯一還原，否則 \(p_i = x\) 或 \(p_i = n + 1 - x\)，視為 \(p_i = x\) 后還原排列，用一次操作 \(2\) 即可確定 \(p_i = x\) 還是 \(p_i = n + 1 - x\) 。

現在目標是求出 \(S_{p_i}\)。

假設我們已經找到了 \(x\) 使得 \(p_x - p_i > 2\)，考慮對于所有 \(y \neq x\) 詢問 \((x,y)\) 會得到什么。若 \(p_y > p_x\) 則得到 \(p_y \oplus p_i\)，\(p_y < p_i\) 得到 \(p_y \oplus p_x\)，\(p_i \leq p_y < p_x\) 時得到 \(p_i \oplus p_x\)。可以發現由于 \(p_x - p_i > 2\) 所以滿足 \(p_i \leq p_y < p_x\) 的 \(y\) 至少有 \(3\) 個。而 \(p_y > p_x\) 時 \(p_y \oplus p_i\) 兩兩不同，\(p_y < p_i\) 時 \(p_y \oplus p_x\) 互不相同，所以在所有結果中出現次數最大的即為 \(p_i \oplus p_x\)，并且可以得到哪些 \(y\) 使得 \(p_y \in [p_i,p_x)\)。

考慮對于所有 \(p_y \notin [p_i,p_x)\) 的 \(y\) 確定 \(p_y > p_x\) 與 \(p_y < p_i\) 哪個成立。任取一個 \(k\) 使得 \(p_k \in [p_i,p_x)\)，分別詢問 \((y,k)\) 與 \((y,x)\)，若 \(p_y > p_x\) 則兩次返回值都是 \(p_y \oplus p_i\)，否則分別是 \(p_y \oplus p_k\) 與 \(p_y \oplus p_x\)。所以只需要判斷兩次結果是否相同即可判定 \(p_y>p_x\) 與 \(p_y < p_i\) 哪個成立。

發現在判定每個 \(y\) 的過程中，若 \(p_y > p_x\) 則可以確定 \(p_y \oplus p_i\)，否則可以確定 \(p_y \oplus p_x\)，而 \(p_x \oplus p_i\) 也已確定，所以對于任意 \(p_y \notin [p_i,p_x)\) 都可以確定 \(p_y \oplus p_i\) 的值。

任取一個 \(z\) 使得 \(p_z < p_i\)，若不存在則意味著 \(p_i = 1\)，對于每個 \(p_y \in [p_i,p_x)\) 詢問 \((z,y)\) 即可得到 \(p_y \oplus p_z\)，又 \(p_z \oplus p_i\) 已知，所以可以確定 \(p_i \oplus p_y\) 的結果。這樣我們得到了所有 \(p_i \oplus p_y\) 的結果，即得到了 \(S_{p_i}\)。

但是還沒完，第一步需要找到一個 \(x\) 使得 \(|p_x - p_i| > 2\) 還沒有做到。由于 \(n\geq 7\)，考慮隨意選出七個不同的數 \(a_1,a_2,\cdots,a_7\)，其中必然存在一個數使得 \(|p_x - p_i| > 2\)，考慮兩兩詢問一次，然后對于每個 \(i\) 判定所有 \((a_i,a_j)\) 返回值中相同的數的最大值是否至少為 \(3\) 即可找到一個符合條件的 \(x\)。

分析詢問次數，確定 \(x\) 的次數為 \(\dbinom{7}{2} = 21\) 次，然后對于每個 \(y \neq x\) 詢問，次數是 \(n-1\)，假設 \(p_y \in[p_i,p_x)\) 的 \(y\) 有 \(c\) 個，則詢問次數為 \(n-c+c=n\)，總次數粗略分析不超過 \(2n+20\)，復雜度 \(O(n \log n)\)，可以通過。

151 P14300

這個題不是很難。

首先確定了哪些位置要選后，貪心地應該從后往前每 \(w\) 個分一組一起運。即每 \(w\) 個算一次貢獻。

對于原問題，直接 DP 是 \(f_{i,j,k}\) 表示 \(i\) 到 \(n\)，最后這組有 \(j\) 個，目前總距離為 \(k\) 的最大權值。復雜度 \(O(n^4)\)。

注意到無論如何總距離不超過 \(\lceil \dfrac{n}{w} \rceil n\)，故 \(k\) 上界就是這個，而 \(j\) 上界為 \(w\)，狀態數只有 \(O(n^3)\)，總復雜度也是 \(O(n^3)\)。

152 P12866

我們聲稱對于偶數 \(n\)，\((x_1,y_1),\cdots,(x_n,y_n)\) 能中 \(k\) 次獎當且僅當以下條件同時滿足：

1. \(\forall 1 \leq i \leq n, x_i + y_i \geq k\)。
2. \(\sum \limits_{i=1}^n \min(k,x_i) \geq \dfrac{nk}{2}\)。
3. \(\sum \limits_{i=1}^n \min(k,y_i) \geq \dfrac{nk}{2}\)。

必要性不難說明，充分性不難歸納說明。

主席樹上二分即可。

153 P12429

神秘猜結論題，畏懼了。大概是每個點最終取值是相鄰 \(O(1)\) 個數正負 \(O(1)\) 的值，然后 DP。

154 P12438

序列從最大值處斷開，然后單側遞歸線段樹板子題吧。

155 NFLS 模擬賽 T3 / P11091

有點意思的題。

直接 DP 是記 \(f_{i,j}\) 表示考慮子樹 \(i\) 內的葉子，最小值為 \(j\) 時，最大值最小是多少。

注意到若存在 \([x,f_{i,x}] \subseteq [y,f_{i,y}]\)，則 \(y\) 沒有意義，將此狀態刪去。我們聲稱只保留有用狀態，且對于每個僅有一個兒子的點直接將狀態繼承，總狀態數就是 \(O(n \log n)\) 的了。

為什么呢。考慮所有至少有兩個兒子的點，并對原樹按照子樹內所有葉子對應集合大小做重鏈剖分。不難注意到對于每個 \(x\)，\(x\) 與 \(f_{i,x}\) 肯定是分屬兩個子樹內的答案。\(x\) 在輕子樹內，狀態數只有輕子樹大小這么多。當 \(x\) 在重子樹時，\(f_{i,x}\) 在輕子樹，此時只有輕子樹大小這么多個 \(f_{i,x}\)，故有效狀態也只有這么多。每個點的狀態數不超過輕兒子大小兩倍，總狀態數 \(O(n \log n)\)。

對于 DP 部分，做 \(O(n2^kk^2\log n)\) 的狀壓 DP 即可。但有 \(k\) 個兒子的點只有 \(O(\dfrac{n}{k})\) 個，這樣分析得到的應該是 \(O(n2^kk\log n)\)。完全跑不滿，可以通過。

156 P12426

不難求出最靠左和最靠右的 B，假設分別在 \(x\) 和 \(y\)。對于每個 \(i \in (x,y)\) 依次判定 \(i\) 上的字符是不是 B。

由于是順次判定，在過程中我們已經得到 \([x,i)\) 和 \([i,y]\) 中 B 的出現次數，不難通過分類討論 \([x,i)\) 和 \((i,y]\) 中 B 是不是眾數以進行判定。

157 P12577

將 LCA 斷開拆成祖先鏈。

一個點 \(x\) 爆了當且僅當 \(x\) 的顏色與給定顏色不同，且 \(t_x \leq dis_u-dis_x+T\)。\(dis\) 是到根鏈長度。不同顏色的最小值這個結構是經典問題，記錄最小值與對應顏色，以及與最小值顏色不同的次小值即可。樹剖容易做到 \(O(n \log^2 n)\)。

158 P12581

這個結構比較顯然是畫在平面上，然后對輪廓線做 DP 就行了，線段樹優化即可。

159 P12038

考慮折半搜索，類似邊分治你如果能找到一條邊盡量劃分均勻那就贏了。

正常做邊分治你要三度化，三度化上連通塊信息無法得以直接保留，不過我們考慮邊分治在點分治上的體現。

選出重心，根據經典結論，此事在 P11988 亦有記載，肯定能對重心的子樹排序后依次選取使得選取的部分在 \([\dfrac{n}{3},\dfrac{2n}{3}]\) 之間，這樣做折半搜索就是 \(O(2^{\frac{2n}{3}}n)\) 了，看起來你可以把 \(n\) 干掉，因為連通信息是可以考慮點邊容斥的，這樣復雜度看起來就更對了。

160 P12357

對于每個點先不考慮選其父親，我們自信地認為選父親不難通過一些換根做出來。

只選子樹那就簡單了，由于你要選兩個子樹，所以必然有一個不是重子樹，那你直接對輕子樹暴力做就行了。

161 P12401

考慮任意兩個對稱的位置 \(i\) 和 \(n-i+1\)，高度分別為 \(x,y\) 且 \(x>y\)，要求即為 \(A>x\) 或 \(B \leq y\)，反之若 \(A \leq x\) 且 \(B>y\)，則不對稱。

相當于限制為若 \(A\leq x\)，則 \(B \leq y\)，又由于 \(B\geq A\)，限制相當于 \(A \in (x,y]\) 時不合法，\(A \leq x\) 時要求 \(B \leq x\)，這個線段樹直接做就行。

162 NFLS 模擬賽 T3

對于相鄰兩個 \(x,y\)，不妨假設 \(x<y\)，最終有 \(\dfrac{1}{2}\) 的概率為 \(x,y\)，也有 \(\dfrac{1}{2}\) 的概率為 \(y,x\)。

若為 \(y,x\)，相當于把 \(x\) 變成了 \(y+0.5\)，然后相當于每相鄰兩個，較小值有 \(\dfrac{1}{2}\) 的概率變為最大值 \(+0.5\)，這個直接計算，數據結構維護之即可。

163 NFLS 模擬賽 T4 / CF1500F

三個值的極差等于兩兩差的最大值。

考慮對原序列的差分 \(d_i=a_{i+1}-a_i\)，則 \(w_i = \max(a_i,a_{i+1},a_{i+2})-\min(a_i,a_{i+1},a_{i+2})=\max(|d_i|,|d_{i+1}|,|d_i+d_{i+1}|)\)。

從前往后 DP，對于每個前綴 \(i\) 維護一個集合表示 \(d_i\) 的所有可能取值。

考慮轉移過程。分類討論 \(|d_i|=w\)，\(|d_{i+1}|=w\)，還是 \(|d_i+d_{i+1}|=w\)，事實上維護連續段結構就可以相當方便維護轉移過程了。

164 CF1784D

考慮這個結構等價于一開始有 \(S=\{1,2,\cdots,2^n\}\)，每次從 \(S\) 中刪去一半的數，最后 \(|S|=1\) 時刪去這最后一個數，要求依次刪去的集合內的最小值單調遞增，對每個 \(i\) 問最后一次刪的是 \(i\) 的方案數。

刪去集合的最小值單調遞增等價于限制每次刪的集合包含整體最小值。然后直接考慮 DP。\(f_{i,j}\) 表示 \(n=i\) 時最后刪去的是 \(j\) 的方案數。轉移直接做是枚舉 \(j\) 之前刪了 \(x\) 個數進行轉移，系數形如 \(\dbinom{j-2}{x-1}\dbinom{2^i-j}{2^{i-1}-x}\)。這個結構不難 NTT 優化。復雜度 \(O(\sum \limits_{i} i2^i) = O(n2^n)\)。

165 CF1784E

總共只有四種比分，\(0/1\) 比 \(0/1\)。

對于確定的串 \(s\)，將四種比分看作四個點，每個比分在經過 \(s\) 后會得到一個新比分，且雙方贏了若干輪。對于每個點向其經過 \(s\) 后得到的比分連邊，邊權為 Alice 的凈勝輪數。這是一個內向基環樹，則比分最終趨近于的結果只依賴于從 \(0\) 比 \(0\) 出發走進的環的邊權和。

對原問題，考慮 DP 套 DP，然而邊權信息不方便記錄，故轉而枚舉最終進入的環的集合，然后在狀態中記每個點的出邊以及環上邊權總和即可。復雜度是 \(O(n^2)\) 乘以一大堆常數。

166 NFLS 模擬賽 T1

反悔貪心基礎練習題。

167 NFLS 模擬賽 T2

總而言之給定 \(w_1,w_2,\cdots,w_k\)，你要計算 \(1\) 到 \(k\) 的排列 \(p_1,p_2,\cdots,p_k\) 滿足 \(p_i \geq w_i\) 的方案數。

按照 \(w\) 從大到小做就好。這里 \(k=O(n^2)\)，所以總復雜度 \(O(k \log k) = O(n^2 \log n)\)。

168 NFLS 模擬賽 T3 / CF715E

先考慮兩個排列 \(p,q\) 確定時的答案。令 \(q=(1,2,\cdots,n)\)，則答案為 \(n\) 減去 \(p\) 的置換環個數。也就是說，對于任意的 \(q\)，對于每個 \(i\) 連邊 \(q_i \rightarrow p_i\)，答案為 \(n\) 減去環數。

現在有若干邊已經確定，加完確定邊后我們得到了若干環和鏈，環固定死了動不了，對于鏈來說，其末尾還需要指定一個出邊。但由于原排列的限制，我們發現對于末尾 \(x\)，若其在 \(q\) 中出現，則其連向的點在 \(p\) 中必然是沒出現的。這個限制很壞，故不妨考慮把所有鏈按照頭尾是否在 \(p\) 中與 \(q\) 中將鏈劃分為 \((0,0),(0,1),(1,0),(1,1)\) 共四類，分別叫做 A，B，C，D。你發現限制形如環上不能有 \(\texttt{BC}\)，\(\texttt{BD}\)，\(\texttt{DC}\) 和 \(\texttt{DD}\)。考慮到這個東西類似第一類斯特林數，考慮其遞推結構，那么先插入 A，B，然后插入 C，最后插入 D，就可以做這個 DP。復雜度 \(O(n^2)\)。

169 CF1726E

考慮置換環的要求，相當于是每個點入邊出邊對應點編號差的絕對值不超過 \(1\)。

不難注意到符合條件的環長只有可能為 \(1,2,4\)，枚舉 \(2,4\) 數量容易做到平方，注意到枚舉 \(4\) 數量后 \(2\) 數量是一個卷積形式，NTT 即可。復雜度 \(O(n\log n)\)。

170 NFLS 模擬賽 T1

對于這種要求相鄰不同的，對于每個前綴只需要記錄本值不同的 \(O(1)\) 種答案即可。

171 NFLS 模擬賽 T2

考慮這個點分治結構在原樹上是沒有什么有意義的過程的。考慮對點分樹的結構 DP。你考慮合并原樹上兩棵子樹，把 \(y\) 為根子樹掛在點 \(x\) 下面。對于點分樹來說，你發現你在做的就是把 \(x,y\) 到根的鏈做合并，所以你的狀態只關心 \(u\) 這個點在點分樹上的深度。這樣就容易做到 \(O(n^2)\) 了。

172 NFLS 模擬賽 T3

\(O(nm)\) 的 DP 是簡單的。記 \(f_{i,j}\) 表示起點為 \((i,j)\) 的答案。轉移枚舉下兩步走到的位置，復雜度 \(O(nm)\)。

注意到，在大多 \((i,j)\)，都有 \(f_{i,j}=f_{i+1,j+1}\)，當且僅當附近曼哈頓距離不超過 \(2\) 的點內有關鍵點時結論失效。證明分類討論不難得到。

那就做完了，把關鍵點附近 \(O(1)\) 個位置拉出來做就行。

173 CF1799F

考慮一些簡單觀察。

對于所數除以 \(2\) 上取整后大于等于 \(b\) 的數從大到小依次進行操作 \(1,2\) 是不劣的。若 \(k_1,k_2\) 一方操作后用完了，那么接下來容易貪心。

現在，所有數除以 \(2\) 上取整后都小于 \(b\)，即所有數 \(<2b\)。不難注意到應該把所有數分為 \((b,2b)\) 之間的以及 \(\leq b\) 兩類。

然后這個最優策略的結構玩一玩就能看出來了，對于 \((b,2b)\) 之間的數，如果有一些只進行操作二，那肯定是小到大排序后一段前綴，而同時進行兩種操作的，肯定是排序后一段后綴。枚舉前后綴長度，剩下的 \(k_2\) 則只能用于 \(\leq b\) 的，肯定是把排序后對應的后綴取走。剩下的 \(k_1\) 從大到小取。復雜度 \(O(n^2)\)。

174 CF1799G

基礎容斥練習題。

對于不能向同組投票的限制容斥。那不就做完了嗎。容斥后的貢獻是一個多重組合數狀物，你只需要對于每組做 DP。這個都是很容易的。復雜度 \(O(n^2)\)，不知道為什么開 \(200\)。

175 CF1799H

有點牛的。

不像一般的樹形 DP 結構。在這個問題中，任意時刻保留的是一個連通塊，這導致你不太容易進行子樹 DP。

斷掉一條邊時，如果選擇進入子樹，則遞歸到一個子樹問題，這是我們希望的。另一方面，如果選擇保留子樹外的部分，你的操作本質是刪掉一個子樹。總之要求選擇的子樹大小為給定的那個值。

每個點為根子樹的操作形態形如先刪去若干子樹，然后進入一個子樹。先只考慮刪掉子樹的要求。記 \(g_{u,S}\) 表示 \(u\) 子樹內要依次操作 \(S\) 這個集合，刪掉了 \(|S|\) 個子樹的方案數。不難通過集合合并轉移。另一方面，考慮原問題的 DP。\(f_{u,i,S}\) 表示 \(u\) 子樹內進行 \(S\) 這個集合的操作，要求第一次遞歸進入子樹是第 \(i\) 次操作。轉移類似。復雜度大概是 \(O(nk3^k)\)。

176 P14343

對 \(r\) 掃描線，對于每個 \(l\) 維護 \([l,r]\) 內和 \(l\) 通信的最大權值。查詢即在 \(r\) 時查詢 \([l,r]\) 區間最大值。

對于 \(r\) 來說，合法的 \(l\) 是一段區間，對于 \(l\) 來說，合法的 \(r\) 是一段區間。所以每個點相當于有一個區間 \([x_i,y_i]\)，新加入 \(r\) 時，考慮區間 \([a,b]\)，要更新所有 \(i \in [a,b],r\in [x_i,y_i]\) 的 \(i\)。隨著 \(r\) 的增大，每個 \(i\) 會經歷激活然后停止激活，然后這就容易使用線段樹維護了。

177 P14346

這個結構比較經典。

考慮先選一個點為根，要求每次在此基礎上再選一個點的情況下怎么做。這個東西是經典的長鏈剖分取前 \(k\) 大狀物。

但是根還沒確定。我們斷言找一組兩個點的最優解并以這兩個點為根分別計算就是答案。我也不會證，看起來就很對。

178 CF1609F

枚舉 \(\mathrm{popcount}=k\)，每個位置會有一個 \(0\) 或 \(1\) 的附加權值，問有多少區間滿足最大值和最小值的附加權值都是 \(1\)。掃描線時維護單調棧不難做到 \(O(n \log n \log V)\)。

怎么干掉一個 \(\log\) 呢？這個有點厲害。注意到對于每個 \(i\)，其做區間覆蓋時，覆蓋的是 \(1\) 當且僅當 \(\mathrm{popcount}(a_i)=k\)，這樣的次數是 \(O(n)\) 的，而覆蓋為 \(0\) 只需要對之前覆蓋的是 \(1\) 的區間進行操作。這樣復雜度是 \(O(n(\log n+\log V))\) 了。

179 CF1609G

有一個 JOI 題和這個類似，貪心的方案一定是，從 \((n,m)\) 倒著走，每次選權值較小的那一側。

那詢問直接對方向切換的位置暴力做即可，線段樹二分。復雜度 \(O(qn \log m)\)。

180 CF1428G2

注意到對于每一位，不等于 \(0,3,6,9\) 中的數至多一個，證明顯然。

所以你可以視為第 \(i\) 位有 \(3(k-1)\) 個重量為 \(3 \times 10^i\) 權值為 \(F_i\) 的物品，對其做多重背包。此外，每一位還可以有任意一個 \(i \in [0,9]\) 可以選，對每一位是一個分組背包。那么先二進制拆分做多重背包，然后做后面的分組即可。