114 全國模擬賽題解

# 114 學年度全國資訊學科能力競賽模擬賽題解 [TOC] ## 工作人員 - 總召：尉崴 - 顧問：陳柏凱 - 題目組：薛尹喆、顏子喬、卓育安、張秉中、蔡兆豐、陳頎恩、黃鼎鈞、曹允碩、陳澔樂、龔德恩、王以安、尉崴、廖衡 - 測題組：蕭凱鴻、高翊恩、黃靖宇、龔德恩、黃傳耀、王品翔 - 系統組：王以安 - 美編組：顏子喬 ## 題本 [zh_TW](https://codeforces.com/gym/106242/attachments/download/34688/Statements%20(zh).pdf) [en](https://codeforces.com/gym/106242/attachments/download/34687/Statements%20(en).pdf) ## [記分板](https://nhspc.cc/2025/ranking/Ranking.html) ## [Upsolving](https://codeforces.com/gym/106242) ## 正式賽 ### A. 尋找襪子 (Socks) ###### author 蔡兆豐 / setter 尉崴 / editorial 尉崴 :::spoiler Subtask 1 可以直接枚舉所有配對情況。 ::: :::spoiler Subtask 2 任意兩隻襪子配對皆可以獲得兩分，所以答案即為 $n$。 ::: :::spoiler Subtask 3 可以先把 $(a_i,b_i) = (a_j,b_j)$ 的 pair 兩兩配對，之後再將剩下的 pair 兩兩配對。 ::: :::spoiler Subtask 4 可以先把 $(a_i,b_i) = (a_j,b_j)$ 的 pair 兩兩配對，之後再將 $a_i=a_j$ 的 pair 兩兩配對。 ::: ### B. 壽司 (Sushi) ###### author 黃鼎鈞 / setter 黃鼎鈞 / editorial 黃鼎鈞 :::spoiler Subtask 1 首先我們注意到有意義的區間最多只會有 $\frac{N(N+1)}{2}$ 個，我們可以 $O(M)$ 預處理，記錄好每個限制有沒有出現過。接下來枚舉 $2^N-1$ 種非空子集，每個子集可以在 $O(N^3)$ 以內檢查好是否符合成本限制及區間限制，總時間複雜度 $O(M+N^32^N)$ 可以通過 ::: :::spoiler Subtask 2 $M=0$ 會把此題簡化為背包問題。考慮 $dp_{i,j}$ 代表僅考慮編號 $1$ 到 $i$ 的壽司，且有選第 $i$ 個壽司，且目前總花費恰為 $j$ 的方法數。 Base case 是 $dp_{0,0}=1$，轉移為 $dp_{i,j}= j \ge a_i \ ? \ \sum_{u=0}^{i-1} dp_{u,j-a_i} : 0$，答案是 $\sum_{i=1}^N \sum_{j=0}^{K} dp_{i,j}$ 總複雜度 $O(N^2K)$。記得模 $998244353$。 ::: :::spoiler Subtask 3 改進一下狀態：考慮 $dp_{i,j}$ 代表僅考慮編號 $1$ 到 $i$ 的壽司，且目前總花費恰為 $j$ 的方法數。 Base case 是 $dp_{0,0}=1$，轉移為 $dp_{i,j}=dp_{i-1,j}+(j \ge a_i \ ? \ dp_{i-1,j-a_i} : 0)$，答案是 $-1+\sum_{j=0}^{K} dp_{N,j}$ 總複雜度 $O(NK)$。 ::: :::spoiler Subtask 4 延續 Subtask 2 的想法，但我們要避免選到共用食材的壽司。如果我們選了壽司 $i$，那上一個選的壽司(也就是轉移來源)不能跟 $i$ 共區間。定義 $pre_i$ 為「所有包含 $i$ 的區間中，左界的最小值」，若沒有區間包含 $i$ 則 $pre_i=i$。我們可以對每個區間暴力更新它包含的所有人的 $pre$。使用跟 Subtask 2 一樣的狀態定義， Base case 是 $dp_{0,0}=1$，轉移為 $dp_{i,j}= j \ge a_i \ ? \ \sum_{u=0}^{pre_i-1} dp_{u,j-a_i} : 0$，答案是 $\sum_{i=1}^N \sum_{j=0}^{K} dp_{i,j}$ 總複雜度 $O(NM+N^2K)$。 ::: :::spoiler Subtask 5 把 Subtask 3 的狀態定義與轉移配合 Subtask 4 的區間處理方式即可通過。 Base case 是 $dp_{0,0}=1$，轉移為 $dp_{i,j}=dp_{i-1,j}+(j \ge a_i \ ? \ dp_{pre_i-1,j-a_i} : 0)$，答案是 $-1+\sum_{j=0}^{K} dp_{N,j}$ 總複雜度 $O(NM+NK)$。 ::: :::spoiler Subtask 6 現在不用管成本限制了，但要加速處理區間的速度。對於每個區間 $[l_i,r_i]$，我們在 $r_i$ 的位置放一個 $l_i$，接著我們把這些數字做後綴 min，做完以後就是 $pre$。定義 $dp_i$ 為只考慮前 $i$ 個壽司時的答案，則 Base case 是 $dp_0=1$，轉移為 $dp_i=dp_{i-1}+dp_{pre_i-1,}$，答案是 $-1+dp_n$ 總複雜度 $O(N+M)$ ::: :::spoiler Subtask 7 利用如 Subtask 6 的方式處理區間算出 $pre$，並以 Subtask 5 的方式動態規劃即可通過。總複雜度 $O(NK+M)$ ::: ### C. 鐵樹銀花 (Flower) ###### author 顏子喬 / setter 廖衡 & 顏子喬 / editorial 顏子喬 :::spoiler Subtask 1 由於 $k = 1$，因此圖就是一棵樹。樹上的最大團一定是某條邊的兩端點，因此掃過每條邊，將兩端的權重和的最大值找出來就好，總時間 $O(n + m)$。 ::: :::spoiler Subtask 2 枚舉 $2^n$ 個子集，檢查每個子集是不是一個團，總時間 $O(n2^n)$ (用 bit trick 的話)。 ::: :::spoiler 一些觀察首先~~觀察到~~最大團是一個 NP Complete 問題，因此在基於大部分人相信的猜想的前提下，是不存在一個多項式時間的演算法，因此勢必是要利用這張圖的特性：是 $k$ 棵樹的聯集去掉一些邊。一個很直接的觀察是不會有一個點數大於 $2k$ 的團，但是在基於大部分人相信的猜想的前提下，最大團並不存在一個對於答案的 FPT 演算法，因此我們需要再更強的特性。上面基本上都是一些廢話，這邊開始才是真正有用的東西。對於一張圖，最少需要把邊集分成幾張圖才可以每張圖都是一個森林，這個參數稱為一張圖 $G$ 的 arboricity $a(G)$。因為森林的導出子圖還是森林，因此對於每個點的子集 $H$ 的導出子圖，都有 $E(H) \le a(G) (V(H) - 1)$。也就是說，對於每個點的子集 $H$ 的導出子圖，平均 degree 是小於 $2a(G)$ 的，因此一定有一個點最小 degree 小於 $2a(G)$。 ::: :::spoiler Subtask 3 有了上面的觀察，我們現在可以考慮以下做法：先把這張圖每次拔除最小 degree 的點，檢查包含這個點的所有團內權重最大的是誰，然後移除所有有這個點的邊。因為這個點的最大 degree 不超過 $2k - 1$，因此直接枚舉 $2^{2k - 1}$ 種組合直接去驗證是不是一個團即可，總時間 $O(n(k^2 + k2^{2k}))$。 ::: :::spoiler Subtask 4 肉眼可見的，時間瓶頸在找到包含這個點的最大權的團，因此這邊介紹兩個做法： 1. Bron-Kerbosch Algorithm 2. 折半枚舉 Bron-Kerbosch Algorithm: 極大團只有 $3^{\frac n 3}$ 個，運用[適當的枚舉](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm)，可以在 $O(n3^{\frac n 3})$ 的時間內找出每一個極大團，把所有極大團的權重取最大值即可。折半枚舉: 考慮將點集分為兩個部分，$A, B$，枚舉 $A$ 內部的每個團，與 $B$ 內部的每個團，並計算權重。接著看 $A$ 內部每個團在 $B$ 內部可以接的團中權重最大的權重，便可以在 $O(n2^{\frac n 2})$ 的時間內做完，詳細的解說可以看 [這題](https://codeforces.com/problemset/problem/1105/E) 的解。總時間 $O(n(k^2 + 2^k))$ 或 $O(n(k^2 + 3^{\frac {2k} 3}))$。 ::: ### D. GL 卷積（Gcdlcm） ###### author 陳頎恩 / setter 陳頎恩 / editorial 陳頎恩 :::spoiler Subtask 1 直接 $O(N^2 \log N)$ 枚舉即可。 ::: :::spoiler Subtask 2 由於 $a_i = b_i = 1$，問題簡化為計算對每個 $1 \le k \le N$ 滿足 $\gcd(i, j) + \text{lcm}(i, j) = k$ 的對數。假設固定兩個 $i, j$，我們要怎麼簡化 $\gcd(i, j) + \text{lcm}(i, j)$？若令 $g = \gcd(i, j)$，則因為 $\gcd(i, j) \cdot \text{lcm}(i, j) = i \cdot j$，我們有 $\gcd(i, j) + \text{lcm}(i, j) = g + \frac{i \cdot j}{g} = g + g \cdot \frac{i}{g} \cdot \frac{j}{g} = g(1 + \frac{i}{g} \cdot \frac{j}{g})$，其中 $\frac{i}{g}$ 與 $\frac{j}{g}$ 互質。我們可以先對 $1 \le k \le N$ 計算滿足 $1 + a \cdot b = k$ 且 $a, b$ 互質的 $(a, b)$ 種類數：由於調和級數性質 $\sum_{1 \le i \le N} \frac{N}{i} = O(N \log N)$，這部分可以在 $O(N \log N)$ 中算完。接著枚舉所有 $g$，並直接查詢剛剛處理好的 $1 + a \cdot b = k$ 數量：一組 $(g, a, b)$ 其實就代表當 $i = ga$、$j = gb$ 時，$\gcd(i, j) + \text{lcm}(i, j) = gk$。這部分同樣利用調和級數性質可以在 $O(N \log N)$ 中算完。 ::: :::spoiler Subtask 3 做到這裡的讀者可能就會開始好奇：滿足 $\gcd(i, j) + \text{lcm}(i, j) \le N$ 的 $(i, j)$ 數量真的有很多嗎？如果仔細分析複雜度，會發現數量其實是 $O(N \log^2 N)$ 量級的！我們先固定一個 $g$ 來看，我們會需要枚舉所有 $1 \le k \le \frac{N}{g}$ 的組合，也就是說需要枚舉 $O(\frac{N}{g} \log \frac{N}{g})$ 種組合。因此，總共的組合數就會是 $\sum\limits_{1 \le g \le N} O(\frac{N}{g} \log \frac{N}{g}) = \sum\limits_{1 \le g \le N} \frac{N}{g} O(\log N) = O(N\log^2 N)$。因為有了上面的性質，所以所有能一一枚舉可能的 $(i, j)$ 的程式都是足夠快的（實際測試總共只會有大約一千萬組），一種實作方法是微調 subtask 2 的方法，改成先對 $1 \le k \le N$ 儲存所有滿足 $1 + a \cdot b = k$ 且 $a, b$ 互質的 $(a, b)$，枚舉 $g$ 時再直接跑過所有 $1 \le k \le \frac{N}{g}$ 的 $(a, b)$，並計算答案。如果你的程式對每種可能的 $(i, j)$ 都會計算一次 $\gcd(i, j)$，那理論上的複雜度會是 $\Omega(N\log^3 N)$，但實際上是可以通過此題的；若實作方法與題解描述的一樣，就只會計算 $O(N\log N)$ 次 $\gcd$，時間複雜度為 $O(N\log^2N)$。 ::: ### E. 第 k 小唯一元素（Unique） ###### author 張秉中 / setter 張秉中 / editorial 張秉中 :::spoiler note 首先觀察到值域不重要，所以以下的說明預設把值域離散化成 1 到 $N$ 之間的數字。 ::: :::spoiler Subtask 1 對於每個詢問，直接暴力掃過他的區間並且拿一個陣列/map 紀錄各元素的出現次數之後直接暴力問複雜度 $O(N Q)$ 或 $O(N Q \log N)$ ::: :::spoiler Subtask 2 對於每個數字分開處理。對於每個數字 $a$ 問題變成在問對於一個區間 $[l_i, r_i]$ ， $a$ 是否只出現一次。最後要問答按時，就找合法的數字中第 $k$ 小的。這可以簡單用一個前綴和計算，或者用某些資料結構處理。複雜度 $O((N+Q) max a_i)$ 這個子題應該會對於另解有一定的幫助如果使用有 log 的莫隊的話也有可能可以通過這個子題。 ::: :::spoiler Subtask 3 對詢問離線，並且做掃描線。把詢問照左界排序之後，從右往左依序加入數字。當加入第 $i$ 個數字 $a_i$ 時，假設上一次 $a_i$ 出現在 $j>i, a_j = a_i$ ，則： - 如果詢問的右界介於 $[i, j)$ ，則 $a_i$ 只出現一次 - 反之， $a_i$ 就不合法所以，掃描線時我們需要維護一個資料結構，支援： - 在 $[l, r)$ 加入一個數字 $a$ - 刪除之前加入的某個 $[l, r)$ 以及其對應的 $a$ - 查詢一個位置 $p$ 所擁有的數字中的最小值可以發現這可以用線段樹套 set/priority_queue $\times 2$ 做到 ::: :::spoiler Subtask 4 莫隊算法，但是正常莫隊直接做的話複雜度為 $O(N\sqrt Q \log N)$ ，因為會需要維護一個 set/pbds/bit 去紀錄第 $k$ 小的數字。理論上出題者有努力好好卡掉有 log 的作法了把 log 壓掉的作法是使用操作跟詢問的不對稱，在莫隊的過程中我們會進行 $O(N\sqrt Q)$ 次修改，但是只會進行 $O(Q)$ 次詢問。所以，如果我們可以找到一個能夠 $O(1)$ 更新，但查詢可以 $O(\sqrt N)$ 的資料結構的話，那複雜度就可以不用 log 了。可以想到維護 $O(\sqrt N)$ 個桶子，第 $i$ 個桶子紀錄 $[i \times \sqrt N, (i+1) \times \sqrt N)$ 中有幾個元素只出現一次。更新時可以 $O(1)$ 更新桶子的數值。而查詢時可以先花 $O(\sqrt N)$ 的時間找出第 $k$ 小的合法元素在那一個桶子中，並且再暴力遍歷該桶子的元素找出答案。複雜度 $O(N \sqrt Q + Q \sqrt N)$ ::: :::spoiler 另解其實這題根本不用帶根號！對於任意一個數字 $x$，考慮其出現在陣列中的位置，假設為 $i_1, i_2, \dots, i_k$，注意到構造三種區間 - 權重為 $-1$ 的：$[1, i_1 - 1]$ 和 $[i_k + 1, n]$。 - 權重為 $-2$ 的：$[i_1 + 1, i_2 - 1], [i_2 + 1, i_3 - 1], \dots, [i_{k-1} + 1, i_k - 1]$。 - 權重為 $+1$ 的：$[1, i_2 - 1]$、$[i_{k-2} + 1, n]$ 和 $[i_1 + 1, i_3 - 1], [i_2 + 1, i_4 - 1], \dots, [i_{k-3} + 1, i_{k-1} - 1]$。則對於任意一組詢問區間 $[l, r]$，如果 $x$ 出現在 $[l, r]$ 恰好一次，那上述區間中完全包含 $[l, r]$ 的區間的權重總和會恰好為 $1$，否則為 $0$。有了以上觀察後就可以考慮對答案二分搜，現在考慮單筆詢問區間 $[l, r]$。假設目前二分搜搜到 $[L, R]$，我們就把 $[L, M]$ 中數字對應到的構造區間都取出來，其中 $M=(L+R)/2$，然後對這些做區間嵌套問題找出總權重，再根據結果決定要往哪邊繼續搜。乍看之下這樣直接做會是 $O(Q N \log^2 N)$，但如果考慮改成用整體二分搜的方式做的話，就可以優化到 $O((N+Q) \log^2 N)$。 ::: ### F. 根號距離和（Rootsum） ###### author 卓育安 / setter 卓育安 / editorial 卓育安 :::spoiler Subtask 1 純暴力，複雜度 $O(NQ)$ ::: :::spoiler Subtask 2 注意到 $\displaystyle \begin{aligned} s_{j+1} &= \sqrt{|x_1 - y_{j+1}|} + \sum_{i=2}^{N} \sqrt{|x_i - y_{j+1}|}\\ &= \sqrt{|x_1 - y_{j+1}|} + \sum_{i=1}^{N-1} \sqrt{|x_i - y_j|}\\ &= s_j - \sqrt{|x_N - y_j|} + \sqrt{|x_1 - y_{j+1}|} \end{aligned}$ 故先用 $O(N)$ 的時間算完 $s_1$ 後，可再花 $O(1)$ 的時間算完 $s_2, \cdots, s_Q$。 ::: :::spoiler Subtask 3 (不正式解說) - Subtask 4 不用排序的版本，複雜度 $O(N + QB)$。 - 不過因為值域較小，賽中被一些「對 $x_i$ 分塊」的解唬爛過。 - 出題者賽後想到一個 $3\times 10^7$ 量級的浮點數 FFT：定義 $c_{val}$ 為 $\{x_i\}$ 中 $val$ 出現的次數，則注意到 $$\left(\sum_{x=-M}^M t^x c_x\right)\left(\sum_{d=-2M}^{2M} t^d\sqrt{|d|} \right) = \sum_y t^y \left(\sum_{x=-M}^M c_x \sqrt{|y - x|} \right)$$ 但八成會 TLE ::: :::spoiler Subtask 4 **觀察**：對於每個詢問 $y$，注意到 $$[y+1, 10^{12}] \subseteq \bigcup_{k=0}^{B} \underbrace{\left[y + 1.01^{4k}, y + 1.01^{4(k+1)}\right)}_{I_k}$$ 其中 $$B = \left\lfloor\frac{1}{4}\log_{1.01} (2\times 10^{12}) \right\rfloor \approx 700 $$ 則 $\sum_{x_i > y} \sqrt{|x_i - y|}$ 可近似為 $\sum_{k=0}^B 1.01^{(2k+1)} \times cnt_k$（因為只題目只要求相對誤差不超過 $1\%$）。預處理後可在 $O(B)$ 的時間內計算完，其中 $cnt_k$ 為落在 $I_k$ 中的 $x_i$ 個數。$\sum_{x_i < y} \sqrt{|x_i - y|}$ 也可用同樣的方法求出。 **預處理**：為了快速求出 $cnt_k$，預處理時需要將 $\{y_j + 1.01^{4k}\}$ 這 $O(QB)$ 個斷點進行排序，然後記錄每個斷點前有幾個 $x_i$，這樣 $cnt_k$ 即為 $y + 1.01^{4k}$ 和 $y + 1.01^{4(k+1)}$ 兩個斷點前 $x_i$ 的數量差，故預處理的複雜度為 $O(N + Q B \log (QB))$。（瓶頸在排序）最後總時間複雜度為 $O(N + QB \log (QB))$，空間複雜度為 $O(N + QB)$。 ::: ### G. DVDlogo（DVDlogo） ###### author 薛尹喆 & 尉崴 / setter 薛尹喆 / editorial 薛尹喆 :::spoiler 觀察首先注意到過程中logo左下角座標的範圍 $0\leq y\leq H-h, 0\leq y\leq W-w$，所以可以把問題簡化為"一個點在長$H-h=H'$、寬$W-w=W'$的矩形中碰撞 ::: :::spoiler Subtask 1 因為$(H'+1)\times (W'+1)\leq H\times W\leq 10^6$，所以可以開$(H'+1)\times (W'+1)(\times 4)$的陣列直接模擬，紀錄logo當前座標yx與方向(四個方向之一)為狀態，如果在碰到角落前跑回之前出現過的狀態，就表示進入循環，永遠不會碰到；否則會碰到。複雜度 $O((H-h+1)\times (W-w+1))\approx O(HW)$ ::: :::spoiler Subtask 2 關鍵字：貝祖定理觀察垂直方向與水平方向有碰撞時間差$k$，再觀察垂直方向與水平方向碰撞的週期分別為$H'$和$W'$，依據貝祖定理，存在(正)整數$a, b$使得$a\times H'-b\times W'=g, g=\pm\gcd(H', W')$ 可以解釋為：("下a次垂直碰撞"與"下b次水平碰撞"的時間差) $=$ ("這次垂直碰撞"與"這次水平碰撞"的時間差)$+g$ 也就是說，若存在時間差$k$，則時間差$k+g$也存在，拓展為時間差$k+n\times g,n\in \mathbb{N}$也存在，若時間差$k+n\times g=0$表示撞到角落，所以最終答案只要檢查$k$是否為$g$的倍數就好。複雜度 $O(\log(\min(H-h, W-w))) \approx O(\log(\min(H, W)))$ ::: :::spoiler 直覺經過若干時間後碰撞時間差最小會shift一個gcd -> 對於初始時間差k，我們可以shift自由多個gcd，最好最後=0 ::: ### H. 又高又大的牆 (Wall) ###### author 蔡兆豐 / setter 尉崴 / editorial 尉崴 :::spoiler Subtask 1 可以枚舉所有的兩個格子的 pair，並做一次 dfs 判斷兩個格子裡面的牆可不可以用一步互相跳到，就可以蓋出一張新的圖。最後用 floyd-warshall 求出全點對的最短距離。 ::: :::spoiler Subtask 2 首先可以觀察到兩點之間的最佳路徑一定是先跳一個遞增的牆的序列再跳一個遞減的序列直到抵達終點。原因是若路徑中有連續三面牆的高度為 $H_1,H_2,H_3$ 且 $H_1 > H_2 < H_3$ 的話一定可以直接從 $H_1$ 跳到 $H_3$ 就可以減少一步，所以這種狀況不會發生。考慮將最佳走法視為由起點和終點跳一個遞增的序列跳到某一個相同的牆，則還可以觀察到在跳到最高的牆那一步之外，其餘的一定都是跳到目前可以跳到最高的牆（如若跳到的牆的高度依序為 $H_1$, $H_2$, $H_3$ 滿足 $H_1 \leq H_2\leq H_3$，但 $H_1$ 能跳到的最高的牆為 $H_0 \geq H_2$，那 $H_1 \to H_0 \to H_3$ 也是合法的序列，因為 $H_0 - H_1 - H_2 - H_3$ 是一條合法的路徑）。所以可以將起點和終點都分別對其他所有牆 bfs，每次擴張到目前可以跳到的最高的牆，就可以算出起點和終點到所有其他牆分別最少需要跳幾步，再取加起來最小的即可。 ::: :::spoiler Subtask 3 可以發現在 $N=1$ 時兩面牆要互相走到的瓶頸在於兩面牆之間高度最高的那面牆。所以可以先知道最佳路徑上高度最高的點的高度至少要大於等於起終點之間最高的牆。因此，在高度還小於中間那面牆時一定會往可以跳到最高的牆跳，而這個可以先倍增處理。假設從起點和終點分別跳到最後一面比中間還矮的牆是 $a$ 和 $b$，可以證明說 $a$ 和 $b$ 只會需要多花一步、兩步或三步來抵達。首先可以很快判斷多花一步的情況（也就是 $a$ 可以直接跳到 $b$），之後若 $a$ 和 $b$ 都可以花一步走到中間最高的牆則就只須多花兩步。若以上都不成立，可以先讓 $a$ 和 $b$ 都跳到可以跳到最高的牆 $a'$ 和 $b'$，則因為 $a'$ 和 $b'$ 之間的牆都比他們矮所以一定可以一步跳到。 ::: :::spoiler Subtask 4 考慮建立一顆重構樹，方法是將每面牆能一步走到比他高的牆中最矮的牆指定為該面牆的父親。可以觀察到對於任兩面牆，對於以那兩面牆作為起終點的所有路徑中高度最大值的最小值為那兩面牆在重構樹上的 $lca$。由於兩面牆之間最佳路徑中的最大高度一定大於等於 $lca$ 的高度，所以可以知道說在高度還沒超過 $lca$ 之前也一定都是跳最高的牆，這一樣也可以倍增處理。一樣假設倍增完走到了 $a'$ 和 $b'$，則一樣可以證明需要多花一步、兩步或三步來抵達。首先可以很快判斷多花一步的情況，之後可以發現如果要用兩步抵達，則 $a'$ 和 $b'$ 要有共同可以一步跳到的點。考慮對於一個點 $c$ 找出可以一步走到他且比他矮的牆是哪些。如果枚舉 $1,2, \dots ,n \times m$ 並每次把該高度的牆和相鄰的牆合併，則在枚舉到 $t$ 時他能一步跳到的即是他所在的連通塊外層一圈的牆。對於 $c$ 可以找出他成為某個連通塊的「外層一圈的牆」的時間點 $c_1,c_2,c_3,c_4$，可以知道說這四個點都在 $c$ 的子樹中且能一步走到 $c$ 的點為 $(c_1,c),(c_2,c),(c_3,c),(c_4,c)$ 這四個點對在樹上路徑的聯集。現在對於一個 $(a',b')$，要找出兩面牆有沒有共同可以一步跳到的牆的條件就是找到某個 $c$ 使得 $c_i$ 在 $a'$ 的子樹中且 $c_j$ 在 $b'$ 的子樹中。考慮建立 dfs order 且進入和離開點 $i$ 的時間點分別為 $in(i),out(i)$。則上面條件等價找到 $in(c_i) \in [in(a'),out(a')]$ 且 $in(c_j) \in [in(b'),out(b')]$。這個條件可以轉為詢問某個矩形內部有沒有至少一個點，所以可以用掃描線 + BIT 做完。 ::: ### I. 又在構 (Construct) ###### author 顏子喬 / setter 施竣耀 / editorial 顏子喬 :::spoiler 先講怎麼構首先先幫每個人找出他的子樹大小，也就是他所有的小孩的子樹大小的和 $+1$，這樣就可以找出整棵樹的根。接著就要幫根指派第一個小孩，為了要讓前序遍歷字典序最小，一定得選該大小數字最小的點當他的第一個小孩，接著沿著前序遍歷遞迴下去再當新的根，延續一樣的方法構造，直到第一個小孩被構號後再去指派第二個小孩。 ::: :::spoiler Subtask 1 每次找數字最小，符合大小限制的點用暴力掃過迴圈找，總時間 $O(N^2)$。 ::: :::spoiler Subtask 2 預先處理好每個大小的點，由編號小到大排，這樣要找符合大小限制又編號最小的點可以 $O(1)$ 找到，總時間 $O(N)$。 ::: :::spoiler author 的話做 unique 不做 construct 的心態是什麼 = =。 construct 可是我特地出的水題欸。 :::