11.5

P7468 [NOI Online 2021 提高組] 憤怒的小 N

計算

對于前者，由于 \(f(i)\) 是 \(k-1\) 次多項式，可以歸納得到其前綴和是 \(k\) 次多項式，于是可以拉格朗日插值做到 \(\mathcal{O}(k^2)\)

對于后者，再化一下式子

現在需要快速計算 \(\sum_{i=0}^{n-1}(-1)^ii^j\)，我們逐位考慮，記 \(g(x,t,c)=\sum_{i=x}^{x+2^t-1}(-1)^ii^c\)，有

\(g(0,t,j)\) 怎么算，考慮遞推，有 \(g(0,t,j)=g(0,t-1,j)+g(2^{t-1},t-1,j)\)

后面兩維狀態是 \(k^2\) 的，這樣可以做 \(\mathcal{O}(m^2\log n)\)，打表發現當 \(x>2^c\) 時，\(g(x,t,c)=0\)，所以只有 \(\mathcal{O}(m)\) 個有用的 \(x\)，于是復雜度就只有 \(\mathcal{O}(\log n+m^3)\)

證明可以歸納

CF1938M Zig-Zag

直接容斥，之后做類似分拆數，直接 SEQ 合并起來即可

P8147 [JRKSJ R4] Salieri

建 ACAM，對于詢問串，拉出來他在 ACAM 上跑所經過的點的集合 \(T\)，\(cnt_i\) 則為代表 \(s_i\) 的節點的 fail 樹上子樹內，在 \(T\) 中的點的個數

考慮二分，建虛樹，發現虛樹上 \(u\rightarrow fa_{u}\) 這條鏈上的 \(cnt\) 都相同，那么只需要數這樣的鏈上有多少點滿足 \(w_i\ge \left\lceil \frac{mid}{cnt} \right\rceil\)，這個可以主席樹維護，總復雜度 \(\mathcal{O}(|T|\log L\log V)\)

P11057 詐騙題

首先可以說明最大操作次數 \(=n+m-1\)，由于每次操作肯定會染色某一行或者某一列，所以最多有 \(n+m\) 次操作，而如果每一行都被染色了，每一列也都不能再染色了，所以最多有 \(n+m-1\) 次操作

隨便構造到這個上界，只需染色任意 \(n-1\) 行，最后把每一列都染色就行了

考慮建二分圖計數，連邊 \(x\rightarrow y\) 或者 \(y\rightarrow x\)，我們發現操作次數最多的時候一定是一棵外向樹，于是可以數無根樹，考慮 prufer 序列，對于左邊的點，其能選的父親一定在右邊，對于右邊的點，其能選的父親一定在左邊，而最后剩下兩個點一定是不同側的點，所以無根樹的方案就是 \(n^{m-1}m^{n-1}\)，總方案就是 \((n+m)n^{m-1}m^{n-1}\)

P11056 Fire and Big

發現膜 \(n\) 相同的只有一個是必敗態，有結論，必敗態的點大小不超過 \(n(\sqrt n+1)\)

考慮一個必敗態的點 \(x\)，其前面和他同余的肯定都是必勝態，考慮每一個這樣的點 \(p\)，能通過完全平方轉移到它的點中必有必敗的，記這個數量為 \(r(p)\)，而對于每一個 \(k^2\le n\)，能從 \(q-k^2\) 轉移到 \(q\) 的必敗點的個數至多為 \(1\)，其中 \(q\) 與 \(x\) 同余，所以 \(\sum_{p<x,p\equiv x}r(p)\le\sqrt n\)，那么這樣的 \(p\) 的數量不超過 \(\sqrt n\)，于是結論得證

直接從每個必敗態往后遞推就行了，復雜度 \(\mathcal{O}(n^{1.5})\)

P11058 合并香蕉

最大化 \(\sum a_ik_i^{-c_i}\)，有結論，當 \(\left\{c_1,c_2,\cdots,c_n\right\}=\left\{1,2,\cdots,n-1,n-1\right\}\) 時最優

假如不滿足上述條件，此時一定存在兩個點，其兒子都是葉子，我們取出所有這樣的點中次深的那個，記作 \(x\)，其兒子為 \(a\) 和 \(b\)，由于是次深的，我們一定能再找到一個和他在同一深度的點 \(y\)，其中 \(y\) 的兒子分別為 \(c\) 和 \(d\)，且 \(c\) 和 \(d\) 中一定有一個葉子，不妨令這個葉子為 \(c\)，而 \(a\) 和 \(b\) 和 \(c\) 都在同一層，所以我們可以仍以調換 \(a,b,c\) 的位置，其答案不變，記 \(v_i=a_ik_i^{-c_i}\)，所以不妨讓 \((1-\frac{1}{k_c})v_c\ge\max((1-\frac{1}{k_a})v_a,(1-\frac{1}{k_b})v_b)\)，現在將 \(c\) 和 \(x\) 交換位置，此時 \(d\) 子樹的答案不變，\(c\) 的深度加一，\(a\) 和 \(b\) 的深度減一，則答案變化 \(\Delta\) 為 \((k_c-1)v_c-((1-\frac{1}{k_a})v_a+(1-\frac{1}{k_b})v_b)\)，而 \((k_c-1)v_c=k_c(1-\frac{1}{k_c})v_c\ge 2(1-\frac{1}{k_c})v_c\ge (1-\frac{1}{k_a})v_a+(1-\frac{1}{k_b})v_b\)，所以此時答案一定更優，發現每次調整之后所有葉子的深度之和加一，于是一定能調整到我們想要的局面，得證

直接二分圖最大全匹配太唐了，發現 \(c_i\) 太大的時候 \(a_ik_i^{c_i}\) 就沒了，所以只保留 \(\mathcal{O}(\log V)\) 個右部點即可，而在 \(k_i\) 相同時，\(a_i\) 較大的一定 \(c_i\) 更小，所以左部點也只需要保留 \(\mathcal{O}(k\log V)\) 個，直接費用流即可

P9818 游戲王

難點在于按照 \(\left\lfloor\frac{v}{i}\right\rfloor\) 劃分等價類，直接貓樹上做背包，容易合并，復雜度 \(\mathcal{O}(n\sqrt V\log n)\)

P11427 [清華集訓 2024] 絕頂之戰

考慮如果我們塞了一個段，他會把整個一維空間分成兩部分，這兩部分互相不影響，所以我們最后放的東西會形成一個二叉樹的結構，我們考慮對這個結構進行 dp

先在外層欽定哪些東西不能選，記這個集合為 \(T\)，在內層，記 \(f_S\) 為 \(S\) 這個集合最長能到多少，終止條件為 \(f_{\emptyset}=\min_{x\in T}a_x\)，記 \(pre_{i}=\min\limits_{0\le j\le i,j\in T}a_j\)，那么 dp 的時候，記 \(S\) 中的最小編號為 \(u\)，必須 \(\sum_{x\in S}a_x<pre_u\)，要不然就寄了，然后把 \(S/\{u\}\) 劃分成兩個子集，轉移 \(f_S\leftarrow f_{T_1}+f_{T_2}+a_u\)，最后令 \(f_s\) 對 \(pre_u\) 取 \(\min\) 即可

復雜度 \(\sum_{i=0}^{n}\binom{n}{i}3^i=4^n\)

P11426 [清華集訓 2024] 比賽

對于一個環，記 \(w_{R<B},w_{B<R},w_{R>B},w_{B>R}\) 四種相鄰位置的情況，最終這個環會貢獻到 \(w_{R<B}+w_{B>R}-w_{R>B}\)，而有 \(w_{R<B}+w_{R>B}=w_{B<R}+w_{B>R}\)，為了方便，我們不如把所有的 \(>\) 都變成 \(<\)，也就是貢獻到 \(w_{R<B}-2w_{B<R}\)，所以我們現在只關心 \(<\) 號了

于是我們可以記 \(f_{x,y}\) 為有 \(x\) 個 \(R<B\)，\(y\) 個 \(B<R\) 的方案，這個顯然不好做，考慮容斥，可以考慮算欽定 \(x\) 個和 \(y\) 個的答案，然后再兩維分別二項式反演，現在考慮如何算欽定 \(x\) 和 \(y\) 的答案

我們可以發現，\(R<B\) 和 \(B<R\) 是互不影響的，所以記 \(g_x\) 為選出 \(x\) 個 \(R<B\) 的方案，\(h_y\) 為選出 \(y\) 個 \(B<R\) 的方案，此時會有 \(n-x-y\) 個連續段，所以 \(f_{x,y}\) 就是 \(g_x\times h_y\times (n-x-y-1)!\)，減一是因為要固定 \(1\) 的位置

最后 ntt 做二項式反演即可，復雜度 \(\mathcal{O}(n^2\log n)\)

P8985 [北大集訓 2021] 魔塔 OL

考慮如何做子問題，即給定一些 \(a,b\)，詢問最小的初始生命值，這看起來就很 exchange argument，我們不妨先把所有 \(a_i\le b_i\) 的放到前面并按 \(a_i\) 排序，這個很顯然，對于后面 \(a_i>b_i\) 的，按 \(b_i\) 倒敘排序，證明考慮 \(\max(a_1,a_1+a_2-b_1)\) 和 \(\max(a_2,a_1+a_2-b_2)\) 中取更小的那個，分討一下：

• 對于 \(a_2>b_1,a_1>b_2\)，此時前者取到 \(a_1+a_2-b_1\)，后者取到 \(a_1+a_2-b_2\)，即取到 \(b_1\) 和 \(b_2\) 中更大的
• 對于 \(a_2>b_1,a_1<b_2\)，此時前者取到 \(a_1+a_2-b_1\)，后者取到 \(a_2\)，后者更小，此時有 \(a_2>b_2>a_1>b_1\)，即取了 \(b\) 更大的
• 對于 \(a_2<b_1,a_1>b_2\)，和上一種情況完全對稱
• 對于 \(a_2<b_1,a_1<b_2\)，這種情況不可能存在

現在我們會做子問題了，且若 \((a_i,b_i)\) 已經排好序，我們可以線性遞推出來答案，還要把這個東西套上四維偏序，感覺很難做

而做高維偏序有一種神奇方法，即對于每一個維度，維護前綴所對應的點的編號集合，用 bitset 存下來，最后把所有維上的 bitset 都與起來，這樣可以做 \(\mathcal{O}(\frac{n^2k}{w})\) 的復雜度

那我們也可以考慮高維偏序的方法，先對原序列按 \((a_i,b_i)\) 排好序，每 \(B=\left\lfloor\log n\right\rfloor\) 個數分一塊，每一塊可以 \(2^B\) 從 highbit 遞推出答案，然后對于每一個塊，我們掃所有的詢問，塊內在詢問區間內的數可以用剛才做高維偏序的方式查詢得到，信息是好合并的，有個細節是有些點時間維的影響是一段區間，不過這個可以塊內排序，做差分掃描線就行，反正我們只需要得到那個集合是啥

總復雜度 \(\mathcal{O}(\frac{n(n+V+q)}{\log n})\)

11.6

CTT 和 JOI 一塊做吧，一直做 CTT 想吐

P7013 [CERC2013] History course

考慮二分答案，我們從小往大填每一個編號，記 \(sup_x\) 為 \(x\) 這條線段能填的最大值，初始 \(sup_i=n\)，我們記 \(cnt_i\) 為 \(sup=i\) 的線段個數，記 \(s_i\) 為 \(cnt\) 的前綴和，假如當前該填 \(i\)，如果存在某個 \(j\)，滿足 \(s_j-s_{i-1}>j-i+1\)，這時候 \([i,j]\) 這中間的數完全不夠填，直接不合法，如果存在 \(j\)，滿足 \(s_j-s_{i-1}=j-i+1\)，這時候一定只能是 \(sup\) 在 \([i,j]\) 中的數填 \(i\)，要不然就不夠了，我們找到這個 \(j\)，并找到 \(cup\) 在 \([i,j]\) 中的數，我們可以說明，此時選擇 \(r\) 最小的線段填上，一定是最優的

結論證明可以考慮歸納，對于 \(i=j\) 的情況，結論顯然成立，對于 \(j>i\) 的情況，如果此時存在兩個線段 \(x\) 和 \(y\) 滿足要求，且 \(R_x<R_y\)，對于所有的 \(z\) 滿足 \(R_z\ge R_x\)，選 \(x\) 能影響到的左端點 \(\le R_x\) 的 \(z\) 肯定比 \(y\) 少，而對于 \(R_z<R_x\)，肯定不存在這樣的點，所以結論得證，這樣我們就得到了 \(\mathcal{O}(n^2\log n)\) 的做法

考慮如何用 ds 去維護，我們把所有線段按照左端點排序，如果選擇了 \(x\) 這個線段填上 \(i\)，可以直接讓一段前綴的 \(sup\) 對 \(i+mid\) 取 \(\min\)，這段前綴就是滿足 \(L_y<R_x\) 的 \(y\)，為啥這樣是對的，因為不交的區間，跟據我們的貪心，一定填的編號更小，所以此時不交的區間不會有影響，所以我們發現 \(sup_x\) 具有單調性，這個東西就能用腳維護了，填 \(i\) 的時候我們還要找到對應的 \(j\)，可以再開一個線段樹維護 \(s_i-i\)，線段樹上二分就行了

復雜度 \(\mathcal{O}(n\log^2n)\)

#2559. Endless Road

離散化，變成每次修改單點，我們發現如果區間 \(i\) 包含區間 \(j\)，那么任意時刻都有 \(t_i>t_j\)，因此我們可以把包含關系去掉，現在對于不包含的單調區間，我們稱其為好的，每次修改單點時，可以二分出他會影響到的好的區間的范圍，直接線段樹就行了，如果一個區間被刪空了，考慮加入新的好的區間，找到這些新區間可以借助兩邊的原有的好的區間，復雜度線性對數

#6878. 生不逢時

首先把回文轉化一下，我們把每個二進制數腰斬再折起來異或，如果 \(m\) 是奇數就把中間那一位去掉，形式化一下就是一個映射 \(f(S)=\sum_{i=0}^{m/2}(S_i \oplus S_{m-i-1})2^i\)，那么 \(S\) 回文當且僅當 \(f(S)=0\)

我們先考慮 \(l_i=0\) 的子問題，考慮把 \([0,x)\) 拆成若干個整區間，每個區間都形如 \([x,x+2^t)\)，我們驚奇的發現，每個整區間在做了映射之后就是某個整區間重復若干次，當 \(t\le m/2\) 時，就是一個整區間，若 \(t>m/2\)，會變成區間 \([0,2^{m/2})\) 重復 \(2^{t-m/2}\) 遍，于是一個 \([0,x)\) 可以看成若干個整區間的線性組合，而兩個區間 \([0,x)\) 和 \([0,y)\) 的答案，就可以看作這些整區間分別做異或卷積再求和在 \(0\) 處的值

由于要對某個前綴求答案，考慮用一個數據結構在線維護，這個東西有天然的分治結構，我們可以用動態開點線段樹去維護這些整區間異或卷積的結果，就是假如有兩個整區間的線性組合 \((F_1,F_2,\cdots,F_n)\) 和 \((G_1,G_2,\cdots,G_m)\)，我們發現 \(F_i\times G_j\) 仍然是一個整區間，如果 \(F\) 和 \(G\) 之間有包含關系，假如是 \(G\subseteq F\)，其會貢獻到 \(G\) 的大小次 \(F\)，沒有包含關系則可以直接貢獻到 LCA，記 \(val_u\) 為線段樹上 \(u\) 這個節點所代表的整區間被貢獻了幾次，再處理 \(sum_u=val_u\times len_u+sum_{ls}+sum_{rs}\)，用于處理不包含區間以及兒子到父親的貢獻，可以在線段樹上可以輕松維護

又考慮到異或 \(=0\)，所以可以 meet in the middle，我們維護兩棵這樣的線段樹，每次加入一個 \([0,r_i]\) 的時候，將其加入更小的那一顆，最后 dfs 算貢獻，具體來說，維護 \(X\) 為 \(u\) 到根鏈上在第一棵樹上 \(val\) 的和，\(Y\) 為 \(u\) 到根鏈上在第二棵樹上 \(val\) 的和，最后如果 \(u\) 是葉子或者掃到了兩棵樹上都是空的節點，累加 \(X\times Y\times len_u\) 到答案，這樣復雜度會就是 \(\mathcal{O}(2^{n/2}m)\)

若 \(l_i\ne 0\)，我們可以差分成 \([0,r_i+1)-[0,l_i)\)，這個是好處理的

分析一下復雜度，合并會出現 \(2^k\) 個節點，合并的復雜度也是 \(2^k\)，不難得到總復雜度 \(\mathcal{O}(m2^{n/2})\)

#6537. One, Two, Three

考慮 \(1,2,3\) 和 \(3,2,1\) 肯定都是取最左邊和最右邊的 \(1\) 和 \(3\)，且對于 \(1,2,3\)，對于 \(1133\) 這種情況，肯定是第一個和第三個匹配，第二個和第四個匹配最優，那么如果 \(1,2,3\) 選了 \(x\) 個，\(3,2,1\) 選了 \(y\) 個，其 \(1-3\) 和 \(3-1\) 的形態就能知道了，現在考慮 \(x,y\) 是不是合法

現在就變成了區間和點做匹配的問題，記 \(f(l,r)\) 為完全在 \([l,r]\) 中 \(1-3\) 區間，\(g(l,r)\) 為在 \([l,r]\) 中的 \(3-1\) 區間，記 \(c(x,i)\) 為前 \(i\) 個位置中有多少 \(x\)，那么有限制是對于所有的 \(l,r\)，有 \(f(l,r)+g(l,r)\le c(2,r)-c(2,l)\)

我們發現 \(f(l,r)=\max(x-c(1,l)-(c(3,n)-c(3,r)),0)\)，\(g(l,r)\) 也同理，這樣我們能得到分別關于 \(x,y,x+y\) 的三個不等式，算就行了

構造方案直接用腳構造就完了

復雜度線性

P8989 [北大集訓 2021] 隨機游走

令 \(f_i\) 為從 \(1\) 走到 \(i\) 的期望步數，那么有 \(f_{i+1}=(f_i+1)\times(d_i+1)\)，因為期望走 \(d_i+1\) 次才能通過 \(i\rightarrow i+1\) 這條邊，于是答案就是

當 \(m<n-1\)，此時給 \(n-1\) 到 \(n-m\) 分別連一條到 \(1\) 的邊最優

否則，有 \(d_i\) 單調，\(d_1\) 是唯一的最小值，極差不超過 \(2\)，這些都不是很好推導，但是我不想再寫一遍公式了，當然也可以打表來的更快，知道了 \(d\) 可以直接算答案，復雜度 \(\mathcal{O}(T\log n)\)

P8991 [北大集訓 2021] 出題高手

666 沒看到數據隨機

把前綴和的 localmax 拉出來，答案只可能以這些東西為端點，然后你又發現區間長度不會太長，可以瞎幾把取個閾值，最后要做的就是單點修改，2-side 矩形求 \(\max\)，分塊即能做到 \(\mathcal{O}(n\sqrt n)\)

P8994 [北大集訓 2021] 經典游戲

巴巴博弈。

SG 值為子樹內的最遠距離，查詢的就是 \(u\) 的一級鄰域以內所有的點中，滿足 \(S_u<d_u\) 的個數，其中 \(S_u\) 為以 \(u\) 為根的答案，\(d_u\) 為以 \(u\) 為根的最長鏈

單點修改時，對 \(S\) 的影響就是子樹異或，可以用樹狀數組維護，而我們又不能時時刻刻維護某個點鄰域的答案，但是發現單點修改時，很少的點和父親的變化是不同步的，所以我們可以考慮維護這個變化量，具體的，每個點開三個數據結構，記錄 \(d_v=d_u+1,d_v=d_u,d_v=d_u-1\) 的點的變化，只需要單點修，查詢時在樹狀數組上問出來 \(u\) 的 \(S\)，然后就是在每一個數據結構上詢問異或上 \(S\) 之后 \(<\) 某個值的數的個數，可以用 01trie 維護

復雜度線性對數

P8986 [北大集訓 2021] 基因編輯

一個 \((x,y)\) 合法當且僅當

• \(\not\exists i<y,a_i=a_x\)
• \(\not\exists i>x,a_i=a_y\)

用腳維護，復雜度線性對數

P14382 [JOISC 2017] 開荒者 / Cultivation

發現每個草都會影響一個相同的矩形，且操作順序無關緊要，所以答案只和這個矩形的 \(l,r,u,d\) 有關，如果兩維都枚舉就太唐了，我們考慮枚舉其中一維，不如枚舉所有可能的 \(u,d\)，這樣每個草都變成了一長列，然后考慮 \(l,r\) 應該取多少，我們從上往下掃每一個本質不同的行，并把能覆蓋的這個行上的那些草的列坐標記下來，排序，假如分別是 \(a_1,a_2,\cdots,a_m\)，那么有 \(l\ge a_1-1\)，還有 \(r\ge C-a_m\) 以及 \(l+r\ge a_{i+1}-a_{i}-1\)，這樣我們能得到三個不等式，分別是 \(l\ge a,r\ge b\) 和 \(l+r\ge c\)，那么這個 \(u,d\) 的答案就是 \(\max(a+b,c)\)。

考慮優化，我們發現，\(u+d\) 相同的圖形總能平移得到，什么意思呢，考慮枚舉這個 \(u+d\) 的值 \(s\)，這樣會有一個新的上下長為 \(R+s\) 的圖形，我們截取其中任意一段 \(R\) 都能對應到原來的一組 \(u,d\)，于是枚舉 \(s\)，不難發現這樣的 \(s\) 只有 \(\mathcal{O}(n^2)\) 種，首先是 \(x_i-1+R-x_j\)，另一種是 \(x_i-x_j-1\)，因為如果取得是別的，我們可以調整到一個上述的情況，這樣一定不劣。

現在就要對于每一個 \(s\)，\(\mathcal{O}(n)\) 算出 \(l+r\) 的最小值，我們不妨把所有的點按照 \(x\) 為第一關鍵字排序，因為我們一個 \(R\) 的方案肯定是選的一段連續區間內的點，把所有本質不同行所對應的斷點拉出來，對應了若干個極小段，即所有的 \(x_i\) 和 \(x_i+s+1\)，把他們排序，如果你一個方案內選了若干個段，其會對每個段都算一遍貢獻，也就是第一段中 \(a,b,c\) 對一個區間取最大值，所以我們掃我們選的段的最左邊的那一個，同時雙指針掃最右邊那個段，使得上下長度能夠到 \(R\)，這樣我們可以用單調隊列維護 \(a,b,c\)。

而每一個本質不同的行都是 \(a\) 上一段區間，于是他的 \(a,b,c\) 可以提前預處理出來，記一個 \(f_{l,r,0/1/2}\) 就行了。

做完了，復雜度 \(\mathcal{O}(n^3)\)。

P14383 [JOISC 2017] 港口設施 / Port Facility

搞笑題，不過這是不是數字樹來著，直接建圖，看一下是不是二分圖就完了，計算一下連通塊數

P14387 [JOISC 2017] 火車旅行 / Railway Trip

不想管倍增了，感覺太難了

考慮把不?？咳魏握灸軌蛑苯踊ハ嗟竭_的點連邊，我們連出來的一定是一張平面圖，因為這是一個笛卡爾樹的結構，考慮三角剖分，做邊分治，算 \(\min(\text{dis}(u,A)+\text{dis}(v,A),\text{dis}(u,B)+\text{dis}(v,B))\)，最短路可以直接跑 bfs，復雜度線性對數

P14392 [JOISC 2017] 都市 / City

太神了，完全不是人

維護 \(dfn_u\) 和 \(siz_u\)，\(dfn\) 我們完整存下來，考慮用較少的數存 \(siz_u\)

我們用一個數列 \(f\) 去逼近 \(siz\)，即對每一個點找到第一個滿足 \(f_i\ge siz_u\) 的 \(i\)，再給 \(u\) 補上 \(f_i-siz_u\) 個虛兒子，這個數列需滿足 \(f_{511}\ge 2^{19}\) 且 \(\sum f_i-siz_u\le 2^{19}-n\)

考慮構造一個等比數列，令 \(f_i=\left\lfloor(1+q)^i\right\rfloor\)，其中 \(q\) 為一實數，這樣每個點加的虛葉子都不超過 \(siz_u\times q\)，由于樹高小于等于 \(19\)，所以總點數不超過 \((1+19q)n\)

可以令 \(f_i=\max(f_{i-1}\times q,1)+f_{i-1}\)，這樣可以節省一些信息

可以任取 \(q\in[0.022,0.045]\)

11.7

模擬賽

T1

T2

T3

T4