Question 1. 「NOI 2025」機器人

給定一張 \(n\) 個點，\(m\) 條邊的有向圖 \(G\)，第 \(i\) 個點連出 \(d_i\) 條邊，其中的第 \(j\) 條邊通向點 \(to_{i,j}\)，代價為 \(c_{i,j}\)，機器人小 R 初始位于點 \(1\)，某參數(shù) \(p\) 初始設定為 \(1\)，上限為 \(k\)。

任意時刻，Controller 可以將參數(shù)進行改寫：

• 若 \(p < k\)，則可以花費 \(v_p\) 將 \(p\) 改寫為 \(p+1\)。
• 若 \(p > 1\)，則可以花費 \(w_p\) 將 \(p\) 改寫為 \(p-1\)。
• 保證 \(v_p, w_p > 0\)。

當小 R 位于點 \(u\)，且 \(p\leq d_u\)，則可以通過第 \(u\) 個點連出第 \(p\) 條邊走向下一個點；否則會卡住走不了。

求小 R 到達每個點要花費的最小代價，代價為經過的所有邊的代價與所有改寫操作的代價的總和。

\(n,m\leq 3\times 10^5, k\leq 2.5\times 10^5\)

這看起來就很最短路，考慮如何建模。

每個點必須在某個特定參數(shù)下才能移動到特定點，這啟發(fā)我們進行分層，對于第 \(i\) 個點，考慮分出 \((d_i + 1)\) 層，前 \(d_i\) 個點表示 \(p = 1, 2, \cdots, d_i\)，最后一個點表示 \(p > d_i\)（記為超限層）。

原 \(G\) 中的每一個點 \(i\) 中的前 \(d_i\) 層，按照 \(v,w\) 將相鄰的層之間進行連邊。

原 \(G\) 中的每一條邊，假設從第 \(u\) 個點的第 \(j\) 條邊到達點 \(v\)，則將點 \(u\) 的第 \(j\) 層向點 \(v\) 的第 \(j\) 層連邊，分兩種情況：

• 若 \(j \leq d_v\)，直接連即可，代價為原邊權。
• 反之，將點 \(u\) 的第 \(j\) 層連向點 \(v\) 的超限層，代價為原邊權；同時再連一條到點 \(v\) 的第 \(d_v\) 層，代價為原邊權加上將 \(p\) 從 \(j\) 改到 \(d_v\) 的最小代價。

最終到達某個點的最小代價為該點的所有層的最小代價，認為 \(m,n\) 同階則時間復雜度大概為 \(\mathcal{O}(m\log_2 m)\)。

Question 2. 「NOI 2025」三目運算符

設長度為 \(n(n\ge 3)\) 的 \(01\) 字符串 \(S\) 的變換 \(f(S)\) 為一個長度為 \(n\) 的字符串 \(T\)：

定義操作為 \(S\gets f(S)\)，可以證明存在一個最小的非負整數(shù) \(k\) 使得 \(k\) 次操作后 \(S = f(S)\)，求出這個最小的 \(k\)。

當然，還給出 \(q\) 次操作，每一次操作給出區(qū)間 \([l,r]\)，表示 \(\forall i\in [l,r]\) 都執(zhí)行 \(S_i \gets 1 - S_i\)，求出操作前與每一次操作后的最小的 \(k\)。

多測，\(T\leq 5, n,q\leq 4\times 10^5, \sum n, \sum q\leq 8\times 10^5\)

對操作的性質不夠敏感，打個表可以發(fā)現(xiàn)如下結論：

Lemma 1

如果存在 \(i\) 使得 \(S_i = S_{i+1} = 1\)，則在 \(S = f(S)\) 時一定有 \(\forall j\in [i,n], S_j = 1\)。

證明：根據(jù)操作，模擬可知每一次會往后多增加一個 \(1\)。

Lemma 2

如果存在 \(i\) 使得 \(S_i = S_{i+2} = 1, S_{i+1} = 0\)，則依次操作后 \(S_{i+1} = S_{i+2} = 0\)。

證明：根據(jù)操作，模擬可知顯然。

Lemma 3

如果存在 \(i,j (i + 2 < j)\) 使得 \(S_i = S_j = 1\) 且 \(\forall k\in (i,j), S_k = 0\)，則 \(S_i\) 影響不到 \(S_j\)。

證明：根據(jù)操作，模擬可知顯然。

Use Them

于是我們可以寫出如下的暴力判斷法則：

1. 找出最小的下標 \(i\) 使得 \(S_i = S_{i+1} = 1\)。
2. 找到最小的下標 \(j\) 使得 \(S_j = S_{j+2} = 1\)。如果 \(i\) 不存在，若 \(j\) 存在則 \(k=1\)（原因是需要一次操作使得所有 \(101\) 中后面的 \(1\) 被消除），若 \(j\) 不存在 \(k=0\)，結束。
3. 找到從 \(i\) 開始的連續(xù)為 \(1\) 的段的結束位置 \(p\)，即 \(\forall k\in [i,p], S_k = 1\) 且 \(S_{p+1} = 0\)。
4. 如果 \(j+2 > i\)，則答案為 \(k = n-p\)（原因是這個相當于就是 \(j\ge i\) 往前推了一個，最終按照引理 1 會全部推平），否則答案為 \(k = \max(n-p, 1)\)（原因是可能后面全是 \(1\)，但是如果前面有一個 \(101\)，就需要多一次操作）。

時間復雜度為 \(\mathcal{O}(nq)\)，要優(yōu)化之，則用線段樹直接維護 \(i,j\)，可能需要同時維護端點值，端點鄰值，區(qū)間長度等等信息，同時 \(p\) 使用區(qū)間和與線段樹二分維護。

每次區(qū)間翻轉，則對應的修改信息即可，時間復雜度為 \(\mathcal{O}(q\log_2 n)\)。

Question 3. Robot Walking

給定 \(n\) 個 checkpoint，第 \(i\) 個 checkpoint 位于 \((x_i,y_i)\) 處，經過一次累計 \(w_i\) 分，多次經過多次累計，保證 checkpoint 的坐標兩兩不同。

Robot 從 \((1,1)\) 出發(fā)，執(zhí)行 \(q\) 次行動操作，每次行動朝 \(x/y\) 的正/負方向移動 \(k_j\) 格，每次行動起始點的 checkpoint 不累計分數(shù)。

求出 \(q\) 次行動累計的得分的總和。

\(n,q\leq 2\times 10^5, x_i,y_i,k_j\in [1,2\times 10^5]\)，任意時刻 Robot 的位置滿足 \(x,y\in [1,2\times 10^5]\)

每一次相當于需要找到某條水平線段或豎直線段上所有點的權值的總和，對 \(x=1,2,\cdots, 2\times 10^5, y=1,2,\cdots, 2\times 10^5\) 開 vector 之后二分即可。

稍微有一點細節(jié)，有四個方向可能代碼略長，時間復雜度為 \(\mathcal{O}(q\log_2 n)\)。

Question 4. 「ROIR 2024 Day1」表格游戲

給定一個 \(h\times w\) 大小的非負整數(shù)矩陣，第 \(i\) 行第 \(j\) 列的值為 \(A_{i,j}\)，另外給出一個正整數(shù) \(s\)，可以從矩陣中刪除若干個整行與若干個整列，使得剩下的元素的和恰好為 \(s\)。

\(h,w\leq 15\)

暴力做法為 \(\mathcal{O}(2^{h+w}hw)\) 其實已經不需要很強的優(yōu)化了。

可以發(fā)現(xiàn)枚舉保留的行，僅需要 \(\mathcal{O}(2^h)\)，其實還可以乘一個很大的式子。

枚舉保留的行后，保留每一列帶來的總和已知，記為 \(B_1, B_2,\cdots, B_w\)，要求選出其中一些滿足總和恰為 \(s\)。

背包肯定不行，搜索就回歸暴力了，考慮折半搜索即可，時間復雜度為 \(\mathcal{O}(2^{h+0.5w})\) 或 \(\mathcal{O}(2^{h+0.5w}w)\)。

Question 5. 「EJOI 2022」Adjacent Pairs

給定一個長度為 \(n\) 的值域為 \([1,n]\) 的正整數(shù)序列 \(A\)，稱序列 \(S\) 滿足性質 P 當且僅當 \(\forall 1\leq i < |S|, S_i \ne S_{i+1}\)，則序列 \(A\) 滿足性質 P。

每一次你可以任意改變序列 \(A\) 中的一項為任意正整數(shù)，操作后序列 \(A\) 也應當具有 P 性質。

直至 \(A\) 序列剩下兩種不同的元素，求最少需要的操作次數(shù)。

\(\sum n\leq 2\times 10^5\)

枚舉奇數(shù)位置上的元素 \(x\)，偶數(shù)位置上的元素 \(y\)，為了計算答案，記 \(O_i\) 表示奇數(shù)位置上 \(i\) 的出現(xiàn)次數(shù)，\(E_i\) 表示偶數(shù)位置上 \(i\) 的操作次數(shù)，則答案至少為 \(n - O_x - E_y\)，即所有不是的元素至少需要 \(1\) 次操作。

但是很快就會發(fā)現(xiàn)一個問題，假設有一長度為 \(len\) 的段，這個段內所有偶數(shù)位置上都是 \(x\)，奇數(shù)位置上都是 \(y\)，則需要額外的次數(shù)（操作不同時進行，所以一定會與旁邊相同），可以證明最小的額外次數(shù)一定是 \(\lfloor{\frac{len}{2}}\rfloor\)。

簡單證明：把這一段拿出來，下標重新編號為 \(1,2,\cdots,len\)，則將所有偶數(shù)位置上的元素改為 \(10^9\)，然后將所有奇數(shù)位置上的數(shù)改成需要的，最后將所有偶數(shù)位置上的數(shù)改成需要的，只要第一步改 \(10^9\) 的元素少了，則根據(jù)鴿巢原理一定有相鄰的一對數(shù)，滿足偶數(shù)位置為 \(x\) 而奇數(shù)位置為 \(y\)，卡住了。

所以，設 \(T_{a,b}\) 表示將偶數(shù)位置上的 \(a\) 改成 \(b\)，奇數(shù)位置上的 \(b\) 改成 \(a\) 的最少額外步數(shù)，則可以通過雙指針掃描所有的 \(X,Y\) 交錯連續(xù)段求得，原因是必須是連續(xù)的一段。

則答案為 \(n - O_a - E_b + T_{a,b}\)，考慮如何求出其最小值，分 \(T_{a,b} > 0\) 與 \(T_{a,b} = 0\) 討論。

\(T_{a,b} > 0\)

由于 \(T_{a,b}\) 進行累加的為若干個僅可能在首尾重合的段，所以這樣的 \(a,b\) 只有 \(\mathcal{O}(n)\) 個，為所有的 \((a_{i+1}, a_i)\)，暴力計算即可。

一定要分清是 \((a_i,a_{i+1})\) 還是 \((a_{i+1},a_i)\)，所以不排除筆者寫錯的情況。

\(T_{a,b} = 0\)

對于某個特定的 \(a\)，若 \(T_{a,b} = 0\)，則對于所有出現(xiàn)在偶數(shù)位置上的 \(a\)，其相鄰的元素必定不為 \(b\)，對每個 \(a\)，稱 \(S_a\) 表示所有不行的 \(b\)，則答案為 \(n - O_a + \underset{b\notin S_a}{\min} -E_b\)。

考慮拿 map 或 multiset 維護所有的 \(-E_b\)，每次對一個 \(a\) 詢問最小值時，先將 \(S_a\) 中所有的 \(b\) 對應的 \(-E_b\) 刪除，然后取出最小值，最后再把刪除的 \(-E_b\) 加回去即可。

時間復雜度為 \(\mathcal{O}(n\log_2 n)\)。

Question 6. 「ROIR 2024 Day1」選擇首都

給定一含 \(n\) 個城市的國家，城市間的道路構成樹形結構，初始不定首都，對首都 \(r\) 為 \(1,2,\cdots, n\) 號城市回答如下問題：

• 將原 \(n-1\) 條道路定向為從靠近首都的城市到遠離首都的城市。
• 添加不超過 \(k\) 條有向道路。
• 記從首都到城市 \(i\) 所經過的最少需要的路徑為 \(f_i\)，最小化所有 \(f_i\) 的最大值。
• 求出這個最小值。

\(n\times k\leq 2\times 10^5\)

部分分：僅回答 \(r=1\)，含 \(20\%\) 的部分分。

首先考慮 \(r=1\) 的情況，看到這個最大值最小化，直接先考慮二分，假設需要 check 答案為 \(x\)。

設計如下貪心：每次找到最深的節(jié)點，記為 \(u\)，假設其深度為 \(d\)，找到 \(d\) 的某個祖先 \(p\)，連接 \(r\) 與 \(p\)，使得 \(r\to u\) 的最短路變?yōu)?\(x\)。

則 \(p\) 為 \(r\) 的 \(x-1\) 級祖先，由“最深”得：\(p\) 的所有子樹均已滿足條件，最優(yōu)性可以感性理解。

考慮用線段樹維護之，由于每一次的深度相當于是 dfs 序上的區(qū)間減，容易用區(qū)間加撤銷操作，時間復雜度為 \(\mathcal{O}(k\log_2 ^2 n)\)。

現(xiàn)已知 \(r=1\) 的答案，接下來考慮換根，假設已知 \(u\) 的答案，要求 \(u\) 的某一子節(jié)點 \(v\) 的答案，則依舊可以通過類似做法計算。

根據(jù)上述，在換根的同時，我們需要計算：

• 每個節(jié)點的深度，若首都 \(u\to v\)，則 \(v\) 子樹內的所有點深度 \(-1\)，而 \(v\) 子樹外的所有點深度 \(+1\)，在線段樹上，容易用三次區(qū)間加減維護與撤銷。
• 換根后的 \(k\) 級祖先，分一點情況討論，設詢問的要求祖先的節(jié)點為 \(x\)：
  • 若 \(x\) 是 \(v\) 的子樹內的節(jié)點，則不變。
  • 若 \(v\) 是 \(x\) 的子樹內的節(jié)點，則需從 \(x\) 向下跳到 \(v\)，容易計算出對應的從 \(v\) 向上跳的次數(shù)（因為原始深度均已知）。
  • 否則，設 \(p\) 是 \(x,v\) 的 LCA，則先從 \(x\) 向上跳到 \(p\) 再向下跳到 \(v\)，綜合上述兩種做法可以求。
• 換根后某個點 \(x\) 的子樹，也是一樣的分情況討論：
  • 若 \(x\) 在 \(v\) 的子樹內，則 \(x\) 的子樹不變。
  • 若 \(v\) 不在 \(x\) 的子樹內，則 \(x\) 的子樹也不變。
  • 否則，令 \(v\) 往 \(x\) 跳一步到 \(w\)，則 \(v\) 的子樹為除去原 \(w\) 的子樹內的所有節(jié)點。
  • 綜上，也容易用區(qū)間加減進行維護與撤銷。不理解可以畫圖參考。

所以再次對每個節(jié)點二分，復雜度為 \(\mathcal{O}(nk\log_2^2 n)\)，能否再優(yōu)化？

可以！給出引理：設 \(f_x\) 為 \(r=x\) 的答案，則 \(u\to v\) 滿足 \(|f_u - f_v| \leq 1\)。

簡單證明：讓 \(v\) 抄 \(u\) 的答案，則最多額外添加 \(v\to u\) 一條邊，此時 \(f_v \leq f_u + 1\)；同理讓 \(u\) 抄 \(v\) 的答案類似得到 \(f_u\leq f_v + 1\)。

故換根時枚舉，省去二分，時間復雜度為 \(\mathcal{O}(nk\log_2 n + k\log_2^2 n)\)。

Question 7. [CF2096C] Wonderful City

給定一個 \(n\times n\) 的正整數(shù)網格，執(zhí)行如下操作：

• 1 i，選中一個未在該類操作中選中的 \(i\)，花費 \(r_i\) 的代價，將第 \(i\) 行的所有數(shù)增加 \(1\)。
• 2 i，選中一個未在該類操作中選中的 \(i\)，花費 \(c_i\) 的代價，將第 \(i\) 列的所有數(shù)增加 \(1\)。

\(\sum n\leq 1000\)

注意到如下性質，執(zhí)行一次 1 i 操作后不改變 \(h_{i,j} - h_{i,j+1}\) 的值；同理執(zhí)行一次 2 i 操作后不改變 \(h_{i,j} - h_{i+1,j}\)，而要求的是所有的 \(h_{i,j} - h_{i,j+1}\) 與 \(h_{i,j} - h_{i+1,j}\) 均不能為 \(0\)。

所以兩類操作是獨立的，可以分別考慮。以下僅考慮 1 i 操作。

設 \(f_{i,0/1}\) 表示考慮完前 \(i\) 行，第 \(i\) 行是否操作，使得前 \(i\) 行沒有上下兩個元素相同，所花費的最小代價。枚舉所有的 \(a_{i,j} - a_{i-1,j}\) 是否存在 \(-1/0/1\)，分別考慮四種轉移（\((i-1,0/1)\to (i,0/1)\)）是否可行，而后進行轉移，初始值為 \(f_{1,0} = 0, f_{1,1} = r_1\)，終態(tài)考慮 \(\min(f_{n,0},f_{n,1})\) 即可。

而 2 i 操作同理，于是時間復雜度為 \(\mathcal{O}(n^2)\)。

Question 8. [CF2112E] Tree Colorings

對于一棵樹 \(T\)，其有根節(jié)點，定義 \(F(T)\) 為滿足如下條件的染色方案的數(shù)量：

• 每一個節(jié)點為黃色、綠色、藍色中的一種。
• 根節(jié)點為綠色。
• 任意藍色節(jié)點 \(u\) 與綠色節(jié)點 \(v\) 間的通路上沒有黃色節(jié)點。
• 任意黃色節(jié)點 \(u'\) 與綠色節(jié)點 \(v'\) 間的通路上沒有藍色節(jié)點。

求可使得 \(F(T) = m\) 的最小的 \(|T|\)。

\(m\leq 5\times 10^5\)，一組測試數(shù)據(jù)內全部輸出。

如何求 \(F(T)\)？合理的染色方案肯定是“上面是綠色，下面是藍色或黃色”，即存在節(jié)點的集合 \(S\)，使得 \(\forall u\in S\)，使得 \(u\) 為根的子樹為全黃或全藍。

設 \(f_{u,0/1/2}\) 表示以 \(u\) 為根下的子樹的染色方案，且 \(u\) 染綠色/黃色/藍色。

則 \(f_{u,1}\) 與 \(f_{u,2}\) 只能從其子節(jié)點 \(v\) 的 \(f_{v,1}\) 與 \(f_{v,2}\) 對應轉移，其中各子樹獨立，所以是乘法。

但是 \(f_{u,0}\) 可以從其子節(jié)點 \(v\) 的任意染色轉移，即可以以 \(f_{v,0} + f_{v,1} + f_{v,2}\) 轉移。

顯然，\(f_{u,1} = f_{u,2} = 1\)，即全部顏色相同，令 \(g_u = f_{u,0}\)，則 \(g_u = \underset{v\in s(u)}{\prod} (g_v + 2)\)。

分析一下，\(g_i\) 的起始值為 \(1\)，所以乘出來全部是奇數(shù)，故 \(m\) 為偶數(shù)無解。

設 \(h_t\) 表示 \(F(T) = t\) 的最小的 \(|T|\)，轉移的要求是把 \(t\) 拆成一堆數(shù)的乘積，故轉移為枚舉 \(t\) 的約數(shù) \(p\)，然后有 \(h_t\gets h_{t/p} + h_{p-2}\)，其中 \(\gets\) 為嘗試更新。

時間復雜度為 \(\mathcal{O}(m\ln m)\)。

Question 9. 「POI 2013」LUK-Triumphal arch

給定一棵 \(n\) 個節(jié)點的樹，Suzune 位于 \(1\) 號節(jié)點上，Kaho 有給節(jié)點染黑的能力，初始樹上僅 \(1\) 號節(jié)點為黑，其余所有節(jié)點全部為白色。

每一輪按照如下順序執(zhí)行：

1. Kaho 選擇 \(k\) 個節(jié)點將其全部染成黑色。
2. Suzune 選擇一個相鄰的節(jié)點并移動至該節(jié)點。

任意時刻，Suzune 走至白色節(jié)點上，則 Suzune 勝；否則當樹上所有節(jié)點全部染成黑色，Kaho 勝。

為了使得 Kaho 勝，求出最小的 \(k\)。

\(n\leq 3\times 10^5\)

首先進行一個注意力觀察，若 \(k = K\) 可以勝利，則 \(k = K+1\) 總是能勝利，方案為每次多出來的節(jié)點染根節(jié)點，其余保持不變的策略即可。

故單調性成立，考慮二分最小的 \(k\)，現(xiàn) check \(k = K\) 時是否可行。顯然，\(K \ge d_1\)，其中 \(d_i\) 表示以 \(1\) 為根時點 \(i\) 的兒子數(shù)。

可以發(fā)現(xiàn)一個引理，就是 Suzune 不會走回頭路，Suzune 一定會一路向下，否則會給 Kaho 一次染色機會而降低自己獲勝的可能。

假設某個點向下連出的點少于 \(K\)，則剩下的染色的點可以染子樹中的點，從而彌補需求。

故設 \(f_u\) 表示在 Suzune 位于節(jié)點 \(u\) 上，且 \(u\) 為默認黑色，則最少需要預先在子樹染色的節(jié)點的數(shù)量。

考慮轉移，不考慮與 \(u\) 直接相連的部分，則有 $ \underset{v\in s(u)}{\sum} f_v$ 個節(jié)點需要預先染色，如果不染完這些所有的預先要求的點，Suzune 就可以嘗試往沒有染完的方向走，這樣就不可能保證 Kaho 的必勝狀態(tài)了。

上述式子中 \(s(u)\) 表示 \(u\) 的兒子的集合，依定義有 \(|s(u)| = d_u\)。

冗余的次數(shù)為 \(K - d_u\)，所以 DP 轉移式為 \(f_u = \max(0, K - d_u + \underset{v\in s(u)}{\sum} f_v)\)，則 check 成功當且僅當 \(f_1 = 0\)。

時間復雜度為 \(\mathcal{O}(n\log_2 n)\)，問題得以解決。

Question 10. [AGC013E] Placing Squares

給定一個長度為 \(n\) 的木板，等長度標刻度 \(1,2,\cdots, n-1\) 對木板 \(n\) 等分。

有 \(m\) 個標記刻度 \(x_1,x_2,\cdots, x_m\)。

現(xiàn)在在木板上若干個正方形木塊，要求：

• 木塊首尾相接，邊緊貼木板，剛好覆蓋完整塊木板。
• 木塊的邊長為整數(shù)個刻度。
• 木塊與木塊的交界處所對應的刻度不能是標記刻度。

對于某種放置方案，其權值為所有木塊的面積的乘積，求所有可能的放置方案的權值總和。

\(n\leq 10^9, m\leq 10^5\)

設 \(f_i\) 表示覆蓋到第 \(i\) 刻度的答案，令開始和結尾分別為第 \(0\) 與第 \(n\) 刻度，則轉移為 \(f_i = \overset{i-1}{\underset{j=0}{\sum}} f_j (i-j)^2\)。

含義是提出當前的最后一段，乘上對應的前面的權值總和求總和。

如果 \(i\) 是標記刻度，轉移后令 \(f_i\) 強制改為 \(0\) 即可，考慮如何優(yōu)化。

如果 \(f_i\) 沒有被強制清零，則 \(A_i = f_i\)，則 \(A_i\) 遞推式已知。

所以當沒有遇到標記刻度的時候有：

列出轉移矩陣，做矩陣快速冪。

如果遇到標記刻度時，同理則有：

類似地做矩陣快速冪即可，時間復雜度為 \(\mathcal{O}(T^3m\log_2 n)\)，其中 \(T = 3\)。

Question 11. 「JOISC 2025 Day1」比太郎之旅 2

給定一個 \(n\times m\) 的山峰群，位置 \((i,j)\) 的山峰的海拔為 \(H_{i,j}\)，著名角色 Bitaro 有一個基于參數(shù) \(L\) 的技能：

• 假設他當前在某個海拔為 \(x\) 的山頂上，可以跳到高度為 \(x + L + 0.5\)，隨后上下左右隨便移動，只要移動在山峰群內部且不會撞到某座山上（即某座山的海拔高于當前高度），最后落在某座山的山頂上。

求解 \(q\) 個問題，從位置 \((a_i, b_i)\) 的山峰的山頂移動到位置 \((c_i,d_i)\) 的山峰的山頂?shù)淖钌俚募寄苁褂么螖?shù)。

\(n,m,q\leq 3\times 10^5\)

使用技能的次數(shù)最小化，至少需要滿足：最少需要達到的高度最小化，可以使用并查集維護最小生成樹后進行樹上鏈 max 查詢，后面的問題可以倍增做。

同時還需要滿足：每一次落點都盡可能高，這個也可以類似的做，按照高度從小到大考慮的時候，當考慮高度為 \(H\) 的時候，用另一個并查集，先合并到高度為 \(H+L\) 的點，然后查詢連通塊高度的 max 對應的點即可。

發(fā)現(xiàn)，后面的每一次的落點也可以倍增做，具體來說，可以維護 \(g_{i,j}\) 表示從某個點 \(i\) 跳 \(2^j\) 步會到達哪一個點。

最后查詢就容易了，通過倍增，確定要達到的目標高度，確定最少需要的次數(shù)，可以在線做，時間復雜度為 \(\mathcal{O}((HW+Q)\log_2 (HW))\)。

Question 12. 「CCPC2022 廣州站」A.Alice and Her Lost Cat

給定一棵 \(n\) 個節(jié)點的樹，以 \(1\) 為根，一只小貓從根以最短路走到某個葉子，每個節(jié)點上有監(jiān)控，你可以執(zhí)行如下操作：

1. 開啟某個節(jié)點 \(i\) 的監(jiān)控，需要花費 \(a_i\) 的代價，檢查小貓是否經過節(jié)點 \(i\)，如果經過，可以得知小貓在該節(jié)點之后的一步的去向。該操作可以執(zhí)行若干次。
2. 選擇一個葉子節(jié)點的集合 \(S\)，搜查 \(S\) 內是否有小貓，需要花費 \(t_{|S|}\) 的代價。該操作只能執(zhí)行至多一次。

\(n\leq 5000, t_i\leq t_{i+1}\)

設出 \(f_{i,j}\) 表示以 \(i\) 為根的子樹下有 \(j\) 個要用操作 2 的葉子節(jié)點，該 DP 難以轉移。

改為設 \(f_{i,j,0/1}\) 表示：以 \(i\) 為根的子樹下，有 \(j\) 個葉子節(jié)點沒有確定，是否存在一個葉子節(jié)點，通過開啟祖先的監(jiān)控來確定。

只要有一個節(jié)點 \(w\) 開啟了監(jiān)控并確定有貓，那么 \(w\) 子樹內有一個葉子可以不需要搜查。

假設要求 \(f_{u,k,0/1}\)，如果 \(u\) 不開監(jiān)控，則：

同時，因為 \(u\) 不開監(jiān)控，而 \(u\) 的祖先無法區(qū)分 \(u\) 的不同兒子，所以 \(f_{u,k,1}\) 當且僅當恰有一個子樹 \(v\) 使得 \(f_{v,k_i,1}\) 取到，則：

如果 \(u\) 開監(jiān)控，那么 \(u\) 的所有兒子的需求均被解決。

假設 \(u\) 是葉子，則：

求答案的時候，由根節(jié)點可以通過不開監(jiān)控確定葉子節(jié)點有貓，其余節(jié)點已經通過各種方式確定，故可以直接視作一個代價為 \(0\) 的，位于節(jié)點 \(0\) 的監(jiān)控。

樹上背包 DP 即可，時間復雜度為 \(\mathcal{O}(n^2)\)。

Question 13. 「THUSC 2015」平方運算

給定一個長度為 \(n\) 的非負整數(shù)序列，執(zhí)行如下 \(m\) 個操作：

• 1 l r，表示在模 \(P\) 意義下令 \(\forall i\in [l,r], a_i\gets a_i^2\)。
• 2 l r，表示求 \(\sum_{i\in [l,r]} a_i\) 的值。

\(n,m\leq 10^5, P\in \{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977\}\)

打表可知，當 \(P\) 取這些特定的數(shù)時，操作 \(1\) 得到的數(shù)字容易進入循環(huán)節(jié)，平均不超過 \(12\) 步可以進入循環(huán)，環(huán)長的 LCA 不超過 \(60\)。

那么我們就有一個很好的做法：

• 每個元素先暴力執(zhí)行 \(12\) 次，然后用循環(huán)節(jié)進行維護。
• 于是可以開兩棵線段樹 \(S_1,S_2\)。
  • \(S_1\) 用于維護目前還沒有進入循環(huán)的元素，剩余的步數(shù)與這些元素的區(qū)間和。
  • \(S_2\) 用于維護在循環(huán)節(jié)內的元素，每個區(qū)間的循環(huán)節(jié)的和，目前在循環(huán)節(jié)中的位置，以及元素的區(qū)間和。
  • 每次在 \(S_1\) 上遞歸，如果當前該區(qū)間有剩余的未進入循環(huán)節(jié)的元素，暴力遞歸進子區(qū)間；否則在 \(S_2\) 上操作即可。

時間復雜度是正確的。