不能再擺了吧

Todolist：118e 的形式化理解方法，做一下 abc426，感覺(jué)有點(diǎn)難度，abc425f 的 poly 做法，149d 的 universal 做法，有交合并的復(fù)雜度證明，1554e 更快的做法。

[ARC149D] Simultaneous Sugoroku

直接上大暴力，那就是分成 \(<0,>0\) 的部分加一個(gè)數(shù)，發(fā)現(xiàn)是值域有交平衡樹(shù)合并。注意相同數(shù)要合并（但他們?nèi)匀淮嬖冢虼艘貌⒉榧硎局赶蛄四膫€(gè)數(shù)）否則復(fù)雜度會(huì)錯(cuò)，我也不知道為什么。

CF1554E.You

先來(lái)一遍莫反轉(zhuǎn)化為計(jì)算倍數(shù)的形式。

實(shí)際上這樣可能并不好做。首先在點(diǎn)上這個(gè)限制會(huì)非常麻煩，嘗試用邊描述限制，發(fā)現(xiàn)每條邊只能給兩側(cè)的某一個(gè)端點(diǎn)做貢獻(xiàn)，大概是一個(gè)給邊定向的過(guò)程，指向的點(diǎn)就是這條邊貢獻(xiàn)到的 \(a\)。

由于我們考慮的是 \(a\) 而不是刪除點(diǎn)的序列，所以只需要考慮定向是否和 \(a\) 構(gòu)成雙射即可，每次根據(jù) \(a=0/1\) 給葉子定向后剝?nèi)~子即可得到唯一的定向因此是雙射，答案總數(shù)是 \(2^{n-1}\)。

現(xiàn)在考慮 \(\gcd\) 的事，我們喜歡剝?nèi)~子，知道葉子的 \(a\) 值只能是 \(0/1\)，如果 \(k>1\) 至少要求所有的點(diǎn)都是 \(k\) 的倍數(shù)，那么葉子必須是 \(0\)，定好這些邊的向后剝?nèi)ニ齻儯紤]新的葉子，因?yàn)槭?\(k\) 的倍數(shù)所以大概也能定出向，但是不能保證是 \(k\) 的倍數(shù)了，也就是，父親邊怎么定向都不對(duì)，那這個(gè) \(k\) 就達(dá)不到，否則也是唯一的方案。還有一個(gè)小問(wèn)題，最后的 \(\gcd\) 還是可能是 \(k\) 的倍數(shù)，但是可以直接判斷的。

剝?nèi)~子表現(xiàn)為拓?fù)渑判颍@樣總復(fù)雜度是 \(\mathcal{O}(n^2)\)，有 \(\gcd(a,b)=\gcd(a,a+b)\)，所以原式的 \(\gcd\) 可以再添上一個(gè) \(\sum a\) 項(xiàng)，這項(xiàng)一定是 \(n-1\)，因此 \(k\) 必須是 \(n-1\) 的因數(shù)，這就是 \(\mathcal{O}(n \sqrt n)\) 的了。

還有判素因子的優(yōu)化，但無(wú)人在意啊！

[ABC213E] Stronger Takahashi

這個(gè)是絕世難題啊，流程就是先從當(dāng)前能到的點(diǎn) bfs 擴(kuò)展能直接走的點(diǎn)。然后打破墻花費(fèi) \(1\) 能到的點(diǎn)是這個(gè)點(diǎn)為中心 \(5 \times 5\) 的矩形扣掉四個(gè)角，這是畫(huà)一下容易知道的。那么就用所有能更新這個(gè)打破墻位置的點(diǎn)更新一下這個(gè)位置再標(biāo)記 vis，因?yàn)椴荒鼙ＷC第一次更新是最優(yōu)的。哎看代碼就很好說(shuō)了。

[ABC318Ex] Count Strong Test Cases

分析能答對(duì)的條件，原問(wèn)題是求的每個(gè)環(huán)上的最小值。那么如果存在一次取不到最小值就不對(duì)，應(yīng)為想要總和不變就需要另一個(gè)數(shù)別的更小，但原答案已經(jīng)是最小的了，所以不存在蒙對(duì)的情況。

發(fā)現(xiàn)答錯(cuò)的條件適合容斥，數(shù)一下 A 答對(duì)的方案數(shù)即可，A 和 B 方案數(shù)是一致的。A 答對(duì)的要求就是對(duì)于每個(gè)環(huán)，最小值一定放在環(huán)中編號(hào)最小的點(diǎn)出發(fā)的那條邊上，同理 B 則是編號(hào)最大的點(diǎn)。那么 A 和 B 同時(shí)滿(mǎn)足的方案數(shù)就容易確定，要求一個(gè)點(diǎn)同時(shí)是編號(hào)最小和最大的點(diǎn)，需要連出 \(n\) 個(gè)自環(huán)，\(Q\) 隨意。

對(duì)于 A 對(duì)的，考慮對(duì)于一個(gè)確定的 \(P\)（也就是環(huán)確定），怎樣的 \(Q\) 合法，對(duì)于一個(gè)環(huán)上填的數(shù)，要求最小點(diǎn)那條邊上放著最小值，其他的可以亂填，也就是 \(c\) 個(gè)點(diǎn)的方案數(shù) \((c-1)!\)，但是還有一個(gè) \(n\) 個(gè)權(quán)值分配的方案數(shù)，也就是 \(\binom{n}{c_1,c_2,\dots c_k}\)，方案數(shù)是 \(n!\prod_{i=1}^k \frac{(c_i-1)!}{c_i!}\) 也就是 \(n!\prod_{i=1}^k \frac{1}{c_i}\)。

那么現(xiàn)在可以 dp 了，設(shè) \(f_i\) 表示考慮了 \(i\) 個(gè)點(diǎn)的劃分成環(huán)的 \(\prod \frac{1}{c}\) 之和，轉(zhuǎn)移就是枚舉這個(gè)環(huán)的大小，需要乘上選點(diǎn)的組合數(shù)和選出點(diǎn)的排列數(shù)（這是個(gè)環(huán)排列）當(dāng)然要?dú)J定是最小值所在的環(huán)。寫(xiě)出就是 \(f_i=\sum_{j \le i} f_{i-j} \frac{(i-1)!}{(i-j)!j}\)。接下來(lái)只需要對(duì)轉(zhuǎn)移進(jìn)行分治 NTT 優(yōu)化即可。

整理 $$f_i=(i-1)!\sum_{0 \le j < i} \frac{f_{j}}{j!} \times \frac{1}{(i-j)} $$

CF1175G.Yet Another Partiton Problem

首先是按 \(k\) 從小到大，一輪一輪的算。

轉(zhuǎn)化為 \(f_i=\min_{j<i} g_j +(i-j) \max_{k=j+1}^i a_k\)，復(fù)雜度會(huì)乘一個(gè) \(k\)。

沒(méi)有決策單調(diào)性，那么可能的優(yōu)化就分治一下，復(fù)雜度乘一個(gè) \(\log n\)。

現(xiàn)在考慮的是左邊的對(duì)右邊的貢獻(xiàn)，是 \(g\) 對(duì) \(f\) 的貢獻(xiàn)吶。

有套路的，對(duì)左邊記一個(gè)后綴最大值 \(suf_i\)，枚舉右邊的元素，記前綴最大值 \(pre\)，那么由于 \(suf\) 右到左不降，可以雙指針求出一個(gè) \(j\)，使得 \(i \ge j\) 時(shí)最大值是 \(pre\)，否則是 \(suf_i\)。

是 \(pre\) 部分的轉(zhuǎn)移是 \(g_{j-1} +(i-(j-1)) \times pre\)，是不是李超樹(shù)吶，是直線(xiàn) \((-j,g_j)\)。

是 \(suf_i\) 部分的轉(zhuǎn)移時(shí) \(g_j+(i-j)suf_{j+1}\)，是不是也是李超樹(shù)吶，是直線(xiàn) \((suf_j,g_{j-1}-(j-1) \times suf_j)\)。

現(xiàn)在問(wèn)題是，是對(duì)于 \(j\) 左側(cè)的插入一種線(xiàn)段而右側(cè)插入另一種線(xiàn)段，如果是好維護(hù)的操作我們會(huì)刪除和插入，但是李超樹(shù)不好刪除，那么將其可持久化，就做好了刪除一段的版本，另外一棵樹(shù)維護(hù)插入的結(jié)果即可。

就是，我們用的是插入一個(gè)區(qū)間的線(xiàn)段的版本，而不是一個(gè)插入所有線(xiàn)段的區(qū)間詢(xún)問(wèn)。不知道為啥有地方要開(kāi) long long，可能是為 \(\inf\) 的 \(f\) 導(dǎo)致的？時(shí)間復(fù)雜度 \(\mathcal{O}(nk\log^2n)\)。

[ARC182C] Sum of Number of Divisors of Product

值域范圍內(nèi)共有 \(6\) 個(gè)質(zhì)數(shù)，記第 \(i\) 個(gè)質(zhì)數(shù)是 \(c_i\)，答案是 \(\prod_{i=1}^6 (c_i+1)\)，考慮加上一個(gè) \(x\) 的影響，設(shè)其各個(gè)質(zhì)數(shù)的指數(shù)是 \(d_i\)，那么新答案就是 \(\prod _{i=1}^6 (c_i+d_i+1)\)。

對(duì)她拆括號(hào)，假設(shè)選了 \((c_i+1)\) 項(xiàng)的集合是 \(S\)，則新的答案就是 \(\sum_S\prod_{i \in S} (c_i+1) \prod_{i \notin S} d_i\)。

對(duì)所有方案求和就是外面再套一層 \(\sum\)，把枚舉 \(S\) 提到外面，如果設(shè) \(f_{S}\) 表示所有方案的 \(\prod _{i \in S}(c_i+1)\) 之和，根據(jù)乘法分配律乘上 \(\prod_{i \notin S} d_i\) 是對(duì)的。但是我要用所有的 \(f_S\)，因此每個(gè) \(S\) 都要有轉(zhuǎn)移，就改成 \(\sum_{T\subseteq S}f_T\prod_{i \in S-T} d_i \to f_S\)。關(guān)注長(zhǎng)度再加上長(zhǎng)度這一位，再枚舉一下轉(zhuǎn)移的數(shù)就可以做到 \(\mathcal{O}(nm3^CC)\)，其中 \(C=6\)。初值是 \(f_{0,S}=1\)，\(S\) 任意。

但是 \(n\) 很大，需要改成矩陣乘法的形式，然后要求的是 \(\le n\) 的，所以再加上一個(gè)前綴和即可。

【UNR 6】小火車(chē)

其實(shí)這個(gè)早就做完了，只是遲遲不寫(xiě)代碼和遲遲調(diào)不出來(lái)拖到了如今。

轉(zhuǎn)化，兩個(gè)集 \(A\) 和 \(B\) 和相等，那么 \(A-B\) 就是 \(0\)。

由鴿巢原理一定有這樣的兩個(gè)集合，因?yàn)?\(2^n>p\)。

看著數(shù)據(jù)范圍想要折半，但是不知道和是多少?zèng)]法折。如果枚舉和，那么就是 \(\mathcal{O}(p2^{\frac{n}{2}})\)。

降維的方法考慮二分：如果 \([l,r]\) 中有合法盒子且一側(cè)沒(méi)有，那么另一側(cè)肯定有，這是有單調(diào)性的。現(xiàn)在。真正的鴿巢原理是什么樣的？如果 \([l,r]\) 中有 \(>r-l+1\) 個(gè)數(shù)，那么肯定有一個(gè)盒子裝了兩個(gè)數(shù)。

現(xiàn)在問(wèn)題是 \([l,r]\) 中放的數(shù)的數(shù)量怎么求，左右各放著 \(2^{\frac{n}{2}}\) 個(gè)和，\(l\) 在增大，\(r\) 在減小，排序分析單調(diào)性雙指針可以做到 \(\mathcal{O}(2^{\frac{n}{2}} \log p)\)，是嚴(yán)格的。

也就是，二分 \([l,r]\)，意思是 \([l,r]\) 中有沒(méi)有一個(gè)和對(duì)應(yīng)了多個(gè)子集，check 可以是 \(2^{n/2}\)，再套個(gè)二分也可以。

枚舉左邊的元素求右邊即可，細(xì)節(jié)有點(diǎn)多，將加起來(lái)要 \(-p\) 的和不用的分開(kāi)算，vector 還要記達(dá)到她的狀態(tài)。

[ARC174E] Existence Counting

方案數(shù)在枚舉哪一位不同后是容易計(jì)算的。優(yōu)化發(fā)現(xiàn)除了前后綴和外是一個(gè)二維數(shù)點(diǎn)，可以用 BIT 簡(jiǎn)單維護(hù)。

[Ynoi Easy Round 2025] TEST_176

變化是 \(\le \lfloor \frac{a_i}{2}\rfloor\) 的乘上 \(-1\) 再 \(+a_i\)，直接平衡樹(shù)，需要值域有交。現(xiàn)在是區(qū)間限制，只需要在 \(l\) 處插入記下點(diǎn)編號(hào)，在 \(r\) 處提取根鏈 pushdown 一遍即可。

Merge 必須 pushdown，相同值要合并，但是如果第二棵樹(shù)有也只會(huì)有一個(gè)，因此不用遞歸合并。最后算的時(shí)候只有初始節(jié)點(diǎn)需要 get 一下，因?yàn)椴粫?huì)把一棵樹(shù)的結(jié)構(gòu)刪碎。記得 pushup 維護(hù)父親，也可以 split 和 merge 時(shí)改，但麻煩。

wow 還有 tag 順序問(wèn)題，冷靜分析即可。

P4463 [集訓(xùn)隊(duì)互測(cè) 2012] calc

記 \(f(i,j)\) 表示選了 \(i\) 個(gè)數(shù)，值域是 \([1,j]\) 的答案。有 \(f(i,j)=f(i,j-1)+j \times f(i-1,j-1)\)。注意初值是 \(\forall j,f_{0,j}=1\)。

\(n\) 小而 \(k\) 大，考慮插值，轉(zhuǎn)移的形式可以歸納證明，\(f(i,j)\) 固定 \(i\) 是關(guān)于 \(j\) 的多項(xiàng)式。

設(shè) \(f_i(j)\) 是關(guān)于 \(j\) 的 \(g(i)\) 次多項(xiàng)式，那么 \(f_i(j)-f_i(j-1)\) 是關(guān)于 \(j\) 的 \(g(i)-1\) 次多項(xiàng)式（經(jīng)典結(jié)論）。

也就是把轉(zhuǎn)移方程 \(i\) 和 \(i-1\) 的放到兩邊，那么右邊是 \(f_{i-1}(j-1) \times j\)，是 \(g(i-1)+1\) 次多項(xiàng)式。因此有 \(g(i)-1=g(i-1)+2\)，那么 \(f(n,j)\) 就是關(guān)于其的 \(2n\) 次多項(xiàng)式。

判斷是不是多項(xiàng)式，不妨先假設(shè)她是，然后模擬一下轉(zhuǎn)移，就像凸性證明一樣。

P10143 [WC2024] 代碼堵塞

設(shè)可見(jiàn)結(jié)果的題目集合為 \(S\)。若 \(i \in S\)，限制是 \(\sum_{j<i,j\in S} t_j+t_i \le T\)，按照 \(i\) 順序做背包即可，在 \(i\) 時(shí)要用確定了前 \(i-1\) 個(gè)數(shù) \(S\) 的方案數(shù)，\(i\) 必選，后面隨意。

若 \(i \not \in S\)，則限制是 \(\sum_{j<i,j \not \in S}t_j+\sum_{j \in S}t_j+t_i \le T\)，事實(shí)上這就是 \(\sum_{j<i} t_j+\sum_{j \in S,j >i} t_j +t_i \le T\)，那么按照 \(i\) 逆序做背包即可。\(i\) 必不選，前面隨意。

[ARC122D] XOR Game

這個(gè)是說(shuō)，做 \(N\) 組匹配，求異或最大值的最小值。二分卻不好 check。因?yàn)?\(A\) 選啥 \(B\) 都能跟著選，當(dāng)然 \(A\) 可以選一個(gè)使得 \(B\) 非得選另一個(gè)，選了這個(gè)后 \(A\) 再選一個(gè)答案就相對(duì)大些，如果這樣做了那也是最大值更小的方案。

直接按位確定，從高到低，如果第 \(i\) 位有 \(k\) 個(gè)數(shù)是 \(1\)，\(k\) 是偶數(shù)，那么一定能做到這一位每組匹配都是 \(0\)。匹配一定是 \(0\) 和 \(0\)，\(1\) 和 \(1\)，也就是匹配集合變小了，要遞歸處理 \(0\) 和 \(1\)，然后答案取最大值，因?yàn)閮蛇叺钠ヅ涠家M(jìn)行，那么一側(cè)更大總答案就是更大的。

否則，這一位要有 \(1\) 了，可以做到只有一個(gè)數(shù)這位是 \(1\) 那他就是最大值。考慮這一位是 \(0\) 和是 \(1\) 的集合，求一下各選一個(gè)數(shù)的異或最小值即可。

P10879 「KDOI-07」對(duì)樹(shù)鏈剖分的愛(ài)

\(u=v\) 平凡。設(shè) \(u<v\)，描述一下這個(gè)過(guò)程，發(fā)現(xiàn) \((v,f_v)\) 是一定要加上 \(w\) 的，如果是兩側(cè)都有至少一條邊的平凡情況自然，祖先后代的話(huà) \(v\) 是深的。從邊界的特性入手遞歸解決問(wèn)題。

那么下一步就是枚舉一個(gè) \(v\) 的父親 \(k\)，以 \(\frac{w}{r-l+1}\)貢獻(xiàn)到 \((u,k)\) 鏈中，遞歸做。

這就可以嘗試寫(xiě)成 dp 了。設(shè) \(f_{u,v}\) 表示操作鏈 \((u,v)\)，邊 \((v,f_v)\) 期望加上的值。轉(zhuǎn)移就像剛才一樣。要求 \(u<v\)，所以枚舉 \(k\) 時(shí)要注意。同時(shí)這個(gè)有點(diǎn)特殊，是從大到小轉(zhuǎn)移，根據(jù)狀態(tài)的正式定義，\(u\) 答案是 \(\sum_{v<u} f_{v,u}\)。\(\mathcal{O}(n^3)\)。

修改形如矩形加，差分，但這個(gè)差分也不太容易，因?yàn)閮删S都倒著做所以前綴和改成后綴和，差分也要換個(gè)方向，同時(shí)矩形邊界記得與 \([l,r]\) 取 \(\min\)，還有就是不能枚舉到 \(j>i\) 了否則前綴和算不全。直接在 dp 數(shù)組上差分是對(duì)的，可能用的都是統(tǒng)計(jì)答案不用的數(shù)吧。

P10880 [JRKSJ R9] 莫隊(duì)的 1.5 近似構(gòu)造

不要管那么多，先寫(xiě) dp。設(shè) \(f_i\) 表示考慮了前 \(i\) 個(gè)值域數(shù)，有若干的區(qū)間的答案。

看起來(lái)轉(zhuǎn)移要枚舉 \(j <l \le r\le i\)，然后 \(f_jw(l,r)\) 轉(zhuǎn)移到 \(f_i\)？。但是顯然將區(qū)間擴(kuò)大不會(huì)使價(jià)值變小。因此可以直接扣著邊界轉(zhuǎn)移，\(f_i=\max_{j<i} f_j w(j+1,i)\)，這樣是 \(\mathcal{O}(n^2)\) 的。

最大值太大了，怎么辦？可以按取對(duì)數(shù)的方式改成求和 dp，這樣也能知道每個(gè) \(i\) 的轉(zhuǎn)移方式，可以記下答案。

形如 \(f_i=\max_{j<i} f_j+w(j+1,i)\)，考慮是否有決策單調(diào)性，很遺憾并沒(méi)有吶。那只能分析這個(gè)問(wèn)題的獨(dú)特性質(zhì)了。思索前幾天的 CF，有沒(méi)有可能，能轉(zhuǎn)移的 \(w\) 就幾個(gè)呢？

考慮和固定的兩個(gè)數(shù)，盡量相近的時(shí)候乘積最大，那么考慮一個(gè)權(quán)值為 \(x\) 的值域區(qū)間 \([l,r]\)，考慮拆開(kāi)她然后不妨認(rèn)為 \(x\) 是偶數(shù)，那么解一下 \(\left (\frac{x}{2} \right )^2 \ge x\) 就知道 \(x \ge 4\) 時(shí)可以拆成兩個(gè)區(qū)間不劣，當(dāng)然奇數(shù)啥的可以細(xì)致討論一下，\(=1\) 的貢獻(xiàn)是 \(0\) 也不用考慮，那么只用考慮 \(w=2,3\) 的區(qū)間。

這樣的區(qū)間全部要考慮嗎？\(f_i\) 意思是 \([1,i]\) 分若干段，那么她與 \(f_{i-1}\) 相比肯定不會(huì)變小，因此 \(f\) 是不降的，所以我們只想要最短的一個(gè)。現(xiàn)在變成 DS 問(wèn)題，再挖掘一些單調(diào)性，固定 \(i\) 后 \(w(j,i)\) 隨 \(j\) 減小而增大，兩個(gè)排列上的區(qū)間包含關(guān)系的話(huà)小的就不用要了。故所求即是 \(\max \le 2\) 的最小的 \(j\)。隨著 \(i\) 右移 \(j\) 不降，可以雙指針，如何判定？掃描值域后，記 \(res_i\) 表示第 \(i\) 個(gè)區(qū)間對(duì)應(yīng)上了幾個(gè)數(shù)，那么加減一個(gè)數(shù)對(duì)應(yīng)在排序后的位置區(qū)間上是一段區(qū)間，可以 SGT。

也可以?huà)呙栊蛄形恢茫看渭尤胍粋€(gè)數(shù)的時(shí)候，只考慮與這個(gè)數(shù)形成的區(qū)間，那么分討一下值域也可以，需要維護(hù)包含當(dāng)前位置的區(qū)間所含有的數(shù)的并集，由于區(qū)間排序后的單調(diào)性更是可以實(shí)現(xiàn)的，用 set 維護(hù)。這樣的區(qū)間是 \(O(n)\) 個(gè)。據(jù)說(shuō)如果用莫隊(duì)則能找到 \(O(n\sqrt m+m)\) 個(gè)區(qū)間。

P8321 『JROI-4』沈陽(yáng)大街 2

排列計(jì)數(shù)方法好多啊。這個(gè)是轉(zhuǎn)成匹配做的，就是 \(A\) 和 \(B\) 一一匹配，一組權(quán)值是 \(\min\) 的乘積。

由于涉及到 \(\min\)，把所有數(shù)放一起排序，設(shè) \(f_{i,j}\) 表示前 \(i\) 個(gè)數(shù)有 \(j\) 對(duì)匹配的答案。最終所求是 \(f_{2n,n}\)，而轉(zhuǎn)移則是先放下這個(gè)數(shù)不匹配或是和前面的一個(gè)數(shù)匹配。選匹配的方案數(shù)是 \(res\) 種，\(res\) 是前面異色未匹配點(diǎn)的數(shù)量，容易根據(jù) \(j\) 算出。匹配則代價(jià)需要在此處計(jì)算而非在前面，否則同一組代價(jià)被拆開(kāi)就不能保證正確性，因此從大到小排序，匹配的話(huà)權(quán)值就是當(dāng)前點(diǎn)的值。做完了。

[ARC205B] Triangle Toggle

操作無(wú)法描述或簡(jiǎn)化（可以改成任意大小的環(huán)取反），嘗試尋找不變量。發(fā)現(xiàn)每次操作后每個(gè)點(diǎn)的黑邊奇偶性不變。

如果無(wú)限制，答案是 \(N(N-1)/2\)，每個(gè)點(diǎn)都出 \(N-1\) 條邊，但是有奇偶性限制后，如果 \(N-1\) 和初始時(shí)這個(gè)點(diǎn)黑邊奇偶性不同就不能有。由于度數(shù)總和是偶數(shù)，所以不合法的點(diǎn)出邊數(shù) \(K\) 最終也是偶數(shù)，減去 \(K/2\) 即可。

猜測(cè)上界可以達(dá)到，事實(shí)上確實(shí)可以。（存疑）如果度數(shù)奇偶性全相同，可以按白邊建圖那么度數(shù)全是偶數(shù)有歐拉回路，也就是若干組環(huán)，都可以取反成全黑。

[ARC205E] Subset Product Problem

考慮折半，也就是將一個(gè) \(x\) 拆成前 \(10\) 位和后 \(10\) 位。對(duì)于插入 \(a_i\)，將其貢獻(xiàn)到前 \(10\) 位的超集中，后 \(10\) 位不變，查詢(xún)則統(tǒng)計(jì)后 \(10\) 位的子集，前 \(10\) 位不變。

具體來(lái)說(shuō)，\(f_S\) 表示 \(S\) 的貢獻(xiàn)，插入 \(S\)，對(duì)于 \(S'\) 滿(mǎn)足 \(S'\) 前 \(10\) 位是 \(S\) 的超集且后 \(10\) 位與 \(S\) 相等的得到貢獻(xiàn)。那么 \(f_S\) 事實(shí)上就是只有前 \(10\) 位是 \(S\) 子集的貢獻(xiàn)和。統(tǒng)計(jì)答案再枚舉子集后就兩部分都是子集然后全對(duì)了。

P14254 分割（divide）

一個(gè) \(S_i\) 一定是對(duì)應(yīng)一段區(qū)間 \([l,r]\)，沒(méi)道理不連續(xù)吧。然后，考慮 \(S_1\) 中的最小深度 \(dep_{b_1}\)，由于交的限制，她必須在所有 \(S\) 中出現(xiàn)，因此有 \(dep_{b_i} \le dep_{b_1}\)，又有不降的性質(zhì)，所以所有 \(b\) 的深度都相同，也就是不會(huì)有子樹(shù)切開(kāi)再切開(kāi)的情況就好做了很多。

那么枚舉一個(gè)深度，并枚舉 \(b_1\)，限制是所有其它子樹(shù)的 \(r\) 都 \(\ge b_1\) 的 \(r\)，同時(shí)要存在 \(=\)，\(S_{k+1}\) 的 \(r\) 是沒(méi)被選的子樹(shù)的 \(r\) 最大值。簡(jiǎn)單分討 \(=\) 在 \(2 \sim k\) 取到還是 \(k+1\) 取到即可。注意要保證解合法。

P14255 列車(chē)（train）

\(1\) 操作是 ban 掉 \(l \le x<y \le r\) 的 \((x,y)\)，\(2\) 操作是問(wèn) \(x\le l<r \le y\) 的 \(p_y-p_x\) 最小值。

詢(xún)問(wèn)怎么做？考慮枚舉 \(y\)，由于 \(p\) 的單調(diào)性，找到最大的 \(x\) 即可。考慮所有覆蓋 \(y\) 的 \(1\) 操作 \((l,r)\)，他們會(huì)使得 \(l \sim y-1\) 的左端點(diǎn)不可用，那么 \(y\) 被 ban 掉的區(qū)間就一直是一段后綴。

因此暴力就比較清晰，記 \(L_i\) 表示 \(i\) 左側(cè)第一個(gè)可用的點(diǎn)，那么修改就是對(duì)于 \(i \in (l,r]\)，\(\min(l-1,L_i) \to L_i\)，查詢(xún)則是 \(\min_{i \ge r}\{ p_i-p_{\min(l,L_i)}\}\)，處理邊界可以令 \(p_0=-\inf\)。

由于出現(xiàn)了 \(\min\)，我們想要二分，嘗試 check \(L\) 是否有單調(diào)性，初始時(shí) \(L\) 單調(diào)的，同時(shí)一直有 \(L_i<i\)，歸納證明，那么修改 \(<l-1\) 的不變，大于 \(l-1\) 的改為 \(l-1\)，這是變小了，因此后部單調(diào)性一直滿(mǎn)足，而對(duì)前面的最大值 \(L_{l-1}<l-1\)，故左側(cè)也仍有單調(diào)性。

那么寫(xiě)一個(gè)維護(hù) \(L\) 的線(xiàn)段樹(shù)和維護(hù) \(p_i-p_{L_i}\) 的線(xiàn)段樹(shù)即可。