2021 全國模擬賽 題解

pA - 2D Chess Without Multiverse Time Travel

Author: toxicpie
Setter: erd1

題目：給定棋盤上皇后的位置，請輸出有多少對皇后互相攻擊。

Subtask 1

暴力枚舉兩個皇后，再枚舉有沒有第三個皇后擋在他們中間。
複雜度：

$O(N^3)$。

Subtask 2

維護四個 map，每個代表第 key 個直（橫、斜）排有 val 個皇后。
答案就是

${\displaystyle \sum \mathtt{\text{val}}-1}$。
複雜度：

$O(N\log N)$。

Subtask 3

抱歉卡了點常數。 ><
畢竟肥的

$O(N\log N)$ 跟瘦的

$O(N\log N)$ 大概差了七八倍的常數，所以官解跑

$0.5$ 秒，時限開

$2.0$ 秒似乎還是卡到了很多人。
順便讓各位練習全國賽被垃圾題卡常的心態調整（Ｘ

官解的做法是把輸入的

$x,y,x+y,x-y$ 存在四個陣列裡面，然後 sort，答案就是四個陣列的 v.end()-unique(v.begin(), v.end()) 的和。 當然，胖一點點可能還是能過，但是開到 set 或 map 或 lower_bound 太多次就會太胖。

複雜度：

$O(N\log N)$。

Sidenote

注意到 unordered_map（或 cc_hash_table 等）的複雜度只有在輸入是隨機的時候才是平均

$O(1)$ 的。在輸入不是隨機的時候，除非自己給雜湊函數，否則很容易被弄到每次插入

$O(N)$。理論上這連第二個子任務都不應該過但是我好像有卡失敗ＱＱ。

---

pB - BGP 劫持

Author: HNO2
Setter: double

題目：給定一張有向無環圖，請判斷是否有一條哈密頓路徑。若有，請輸出一個。

Subtask 1

$O(n!)$ 枚舉所有可能的路徑，再檢查相鄰兩項有沒有邊

Subtask 2

可以觀察得到 DAG 上的 Hamilton 路徑存在若且唯若拓樸排序唯一，此時的拓樸排序就會恰為其 Hamilton 路徑，於是

$O(n)$ 求出拓樸排序並檢查即可。

---

pC - 十字架

Author: SorahISA
Setter: casperwang

題目：給定一個矩陣，請計算有多少個十字形區域滿足左右臂等長，上臂比下臂短，且最大值發生在交叉點。

Subtask 1

只要考慮上下的情形即可，對每個權重大於左右兩邊的中間位置，用單調隊列找出一個位置可以分別大於上下的多少格並用 Subtask 5 的算式計算答案。

Subtask 2

對每個位置，

$O(N+M)$ 暴力找出可以分別大於上下左右的多少格，令其個數分別為

$U$、

$D$、

$L$、

$R$，接下來就以下面算式

$O(N)$ 計算出答案。

$$ans=\sum _{i=1}^D(min(L,R)\times min(U,i))$$

總複雜度是

$O(NM(N+M))$

Subtask 3

期待看到神奇的唬爛作法(?)

Subtask 4

用單調隊列找出一個位置可以分別大於上下左右的多少格，並以 Subtask 2的方法計算答案。

Subtask 5

計算答案的公式可以優化如下

$$ans=\{\begin{array}{l}\text{if }U\ge D\text{, }min(L,R)\times \sum _{i=1}^D{i}^2\\ \text{else, }min(L,R)\times (\sum _{i=1}^U{i}^2+U\cdot (D-U))\end{array}$$

總複雜度是

$O(NM)$

---

pD - AI 猜拳

Author: SorahISA
Setter: SorahISA

題目：有

$N$ 輪猜拳比賽，請構造出一個循環出

$M$ 個拳的方法，使得可以贏過固定出拳的對方，且

$(\mathrm{勝}\mathrm{場}-\mathrm{敗}\mathrm{場})$ 盡量小。有

$T$ 筆測資。

• $T\le 100$。
• $1\le M\le N\le 10000$。

Subtask 1

限制：

$N\le 100$；

$M=1$。

既然

$M=1$，那出的拳只會有三種可能，只要分別計算出剪刀、石頭、布分別會得幾分就可以 AC 了！

時間複雜度：

$\mathcal{O}(3N)$。

Subtask 2

限制：

$N\le 100$；

$M\le 8$。

對於一組給定的拳，顯然你可以在

$\mathcal{O}(N)$ 時間得出他的分數：

int N, M;
string X, Y; /// 對方的拳是 X；你的是 X

int score = 0;
for (int i = 0; i < N; ++i) {
    if ((X[i%M] == 'R' and Y[i] == 'P') or
        (X[i%M] == 'P' and Y[i] == 'S') or
        (X[i%M] == 'S' and Y[i] == 'R')) --score; /// lose
    else if (X[i%M] != Y[i]) ++score; /// not lose and not tie
}

所以只要枚舉所有出拳的方法就可以 AC 了！

時間複雜度：

$\mathcal{O}(3^{M}N)$。

Subtask 3

限制：

$N\le 1000$。

觀察出愛一個位置

$p$ 的拳

$Y_p$ 只會對應到天衣

$X_p,X_{p+M},X_{p+2M},\dots ,X_{p+kM}\mathbf{\text{for }}p+kM<N$ 的拳，匹配的位置都是固定的，所以能先處理出在位置

$p\in [0,M)$ 出三個拳會得到的分數

$r_i$、

$p_i$、

$s_i$ 再進行後續的運算。

現在題目被簡化成如下的樣子：給你

$M$ 個三選一，分別可以獲得

$r_i$、

$p_i$、

$s_i$ 分（

$|r_i|,|p_i|,|s_i|\le \lceil \frac{M}{N}\rceil$），請問要讓總和

$>0$ 的總和最小值是多少？

是經典的背包題，透過 DP 來處理可以組成的數字。令

$\mathtt{\text{dp}}[i][j]$ 代表前

$i$ 組的所有

$3^{i+1}$ 種可能性中存不存在可以達到

$j$ 分的取法，有轉移式

$$\mathtt{\text{dp}}[i][j]=\mathtt{\text{dp}}[i-1][j-r_i]\vee \mathtt{\text{dp}}[i-1][j-p_i]\vee \mathtt{\text{dp}}[i-1][j-s_i]$$

最後就

$\mathcal{O}(N)$ 找到最小的位置

$j>0$ 使

$\mathtt{\text{dp}}[M-1][j]=\mathtt{\text{true}}$ 再把解回溯回來就好了。

請記得處理邊界、超出範圍的問題，且要把

$\mathtt{\text{dp}}$ 陣列平移

$N$ 格，因為你也會需要負數的位置。

時間複雜度：

$\mathcal{O}(NM)$。

Solution

上面 DP 的轉移式是經典的湊數字背包問題，可以使用

$\text{color}red\mathtt{\text{std::bitset}}$ 來優化。因為只是語法問題，所以直接上 code：

bitset<2*maxn+1> dp[M+1];
dp[0][maxn] = 1;
for (int i = 1; i <= M; ++i) {
    auto [winR, winP, winS] = win_val[i-1];
    if (winR > 0) dp[i] |= dp[i-1] <<  winR;
    else          dp[i] |= dp[i-1] >> -winR;
    if (winP > 0) dp[i] |= dp[i-1] <<  winP;
    else          dp[i] |= dp[i-1] >> -winP;
    if (winS > 0) dp[i] |= dp[i-1] <<  winS;
    else          dp[i] |= dp[i-1] >> -winS;
}

時間複雜度：

$\mathcal{O}(\frac{NM}{\mathtt{\text{bitset}}})$，在這裡

$\mathtt{\text{bitset}}$ 是

$32$。

去年的全國賽也有需要使用

$\mathtt{\text{bitset}}$ 來優化的題目，可以參考看看 >////<。

---

pE - 地獄屋萬人空巷

Author: erd1, double
Setter: enip
Statement: joylintp

題目：有一些組別在排隊，有兩種操作：

1. 問第
   $k$ 個人是誰。
2. 讓前
   $k$ 組人出隊，並讓後面所有人數小於這
   $k$ 組人總和的組別旋轉。

Solution

要怎麼知道第

$k$ 個人是誰呢？首先我們要找到第

$k$ 個人在第幾組。這可以用 BIT / 線段樹之類的作到。

接下來，我要知道，對於這一組，它被旋轉了幾次。然後我們可以發現，對於同樣長度的隊伍，被旋轉的次數是一樣的。因此我們只要對每個長度

$x$ 都知道它被旋轉了幾次就好！而這東西也是 BIT / 線段樹可以解決的事情。

操作 2 的時候，就是對兩個資料結構單點/區間加值之類的，取決於你用了哪種資結。

---

pF - 地洞遊戲

Author: HNO2
Setter: HNO2

題目：給定一棵有根樹，這棵樹不計根節點一共有

$K$ 個葉子。每個葉子

$i$ 有一個數字

$a_i$，其中

$i$ 必定是

$a_i$ 的祖先。建一張

$K$ 個節點的新有向圖，其中

$i\to j$ 有連邊若且唯若

$a_i$ 同時是

$i$ 和

$j$ 的祖先。問新圖有沒有一條哈密頓路徑，如果有的話輸出任意一條。

Subtask 1

注意到葉子數量很少，所以可以暴力找出新圖有哪些邊以後，再對新圖做哈密頓路徑的位元 DP。

找新圖的邊的部份可以使用對每個

$a_i$ 做一次 DFS、對每個點暴力找出所有祖先後再判斷，或其他

$O(NK)$ 的作法也可以。當然其他時間複雜度更低的作法也可。

找哈密頓路徑的部份是經典問題，可以在

$O(K^2{2}^K)$ 的時間內做完。

Subtask 2

這個 Subtask 以後需要用到一個性質：如果原問題有解，則一定有一個解是將所有葉子依照某個 DFS 順序而成。（簡略說明見下方）

因此可以發現對於定根

$v$ 來說，最多只有一個子樹，他的所有葉子走完以後無法回到

$v$ 或他的祖先，而這個子樹要留到最後再走。而根據這個 Subtask 的限制，沒有與

$v$ 建邊的子樹就是無法回到

$v$ 或他的祖先的子樹（可以稍微想一下），因此就可以據此找出一個合法的順序了。

Subtask 3

有了上面那個性質以後，可以發現最多只有一個子樹，他的所有葉子走完以後無法回到

$v$ 或他的祖先。所以對於每個子樹我們想要找出走完這棵子樹以後可以走到的最淺深度。

使用樹 DP。令

$dept{h}_v$ 為

$v$ 的深度，且令

$d{p}_v$ 為繞完這棵子樹後可以回到的最淺深度。轉移如下：

• 如果子樹中有至少兩個
  $d{p}_{son}$ 都大於
  $dept{h}_v$，則其中一個繞完以後就回不了另一個了，必定無解。
• 如果子樹中恰有一個
  $d{p}_{son}$ 大於
  $dept{h}_v$，則這個子樹要放到最後才走，
  $d{p}_v=d{p}_{son}$。
• 如果子樹中沒有
  $d{p}_{son}$ 大於
  $dept{h}_v$，則任意一個子樹都能當最後一個走到的，由於我們要深度最淺的，因此
  $d{p}_v$ 就是所有
  $d{p}_{son}$ 的最小值。

要構造一組解也十分容易，記住哪個子樹要最後走以後，剩下的子樹依照任意順序繞即可。時間複雜度為

$O(N)$。

Subtask 2 性質簡略說明

考慮給定根

$v$ 底下的所有葉子順序，令

$lea{f}_1,lea{f}_2,\cdots ,lea{f}_m$ 是一個合法的順序。假設兩個不相交葉子區間

$[l_1,r_1],[l_2,r_2]$ 都隸屬於同一個子樹，且兩個區間都和他們相鄰的葉子都屬於不同子樹的話，那把兩個區間併起來，其他相對順序都不動也會是合法順序。這是因為

$lea{f}_{r_1}$ 和

$lea{f}_{r_1+1}$ 屬於不同子樹，

$a_{lea{f}_{r_1}}$ 必為

$v$ 的祖先，故也能抵達

$lea{f}_{l_2}$。用同樣方式也能證明其他接口起來是好的。

這樣持續交換下去就能讓同一棵子樹底下的葉子全部併在一起。之後對每個子樹遞迴做下去就是一個原樹的 DFS 順序了。

---

pG - 蛋餅騎車車

Author: erd1
Setter: erd1

題目：已知區域的地形分布是帶狀的，在每一個區域的移動速率是定值。請問兩點之間的（時間）最短距離。

Subtask 1

距離除以速度加起來不虧。
複雜度

$O(N)$。

Subtask 2

路徑一定是在地形交界處轉折，而且轉折點對時間的函數是凸（或凹）的。
因此可以對他三分搜。
複雜度

$O(\log \epsilon )$。

Subtask 3

這題其實是物理題。司乃爾定律告訴你最短路徑一定滿足

$\sin {\theta }_i/v_i$ 是定值。對起始角或起始

$\sin$ 或隨便什麼的做二分搜牛頓迭代都會過。
複雜度

$O(N\log \log \epsilon )$。

Subtask 4

最後是精度問題。

你只要想像如果有一塊的速度超大，其他都超小，那你在其他段的路徑應該幾乎是平的，然後只有在那一段超斜。所以如果你在其他段的角度稍微動一下，你在那段的角度應該會動超級多，然後你就噴掉了。

對最斜的那段的角度二分搜也是沒用的，因為你的角度會很接近

${90}^{\circ }$，所以角度稍微動一下，你的

$\tan \theta$ 也會動超多（你可以看看

$\tan$ 的函數圖形），他還是會噴掉。

因此正確的做法應該是求出

$\tan \theta$。你可以證明

$\tan \theta$ 只需要

${10}^{-9}$ 的精度左右即可。

Proof

Let

$C=\sin {\theta }_i/v_i$, then the answer is given by

$$y=f(C)=\sum x_i\tan {\theta }_i=\sum \frac{x_{i}C{v}_i}{\sqrt{1-C^2{v}_i^2}}$$

To calculate the root

$C$ to a precision of

$\epsilon =\left|\mathrm{\Delta }C/C\right|$, we may implement a binary search to do so in

$O(N\log \epsilon )$. However, to calculate the answer to a precision of

${10}^{-6}$, we would need a precision of

${10}^{-27}$ in the worst case, which is not desirable.

你只要想像如果有一塊的速度超大，其他都超小，那你在其他段的路徑應該幾乎是平的，然後只有在那一段超斜。所以如果你在其他段的角度稍微動一下，你在那段的角度應該會動超級多，然後你就噴掉了。

對最斜的那段的角度二分搜也是沒用的，因為你的角度會很接近

${90}^{\circ }$，所以角度稍微動一下，你的

$\tan \theta$ 也會動超多（你可以看看

$\tan$ 的函數圖形），他還是會噴掉。

因此正確的做法應該是求出

$\tan \theta$。你可以證明

$\tan \theta$ 只需要

${10}^{-9}$ 的精度左右即可。

About precision

Suppose

$v_i$ is descending, and

$\sin {\theta }_1/v_1=C$.
We ought to calculate

$$T(C)=\sum \frac{x_i}{v_i\cos {\sin }^{-1}(C{v}_i)}=\sum \frac{x_i}{v_i\sqrt{1-C^2{v}_i^2}}$$
Thus if

$C$ has an error of

$\mathrm{\Delta }C\ll C$,

$T(C)$ has an approximate error of

$$\mathrm{\Delta }T\approx \frac{\mathrm{d}T}{\mathrm{d}C}\mathrm{\Delta }C=-(\sum \frac{x_{i}C{v}_i}{{\sqrt{1-C^2{v}_i^2}}^3})\mathrm{\Delta }C$$

And thus

$$\left|\frac{\mathrm{\Delta }T}{T}\right|\gtrsim \frac{x_{1}C{v}_1/{\sqrt{1-C^2{v}_1^2}}^3}{(\sum x_i/v_i)/\sqrt{1-C^2{v}_1^2}}|\mathrm{\Delta }C|=\frac{x_1{C}^2{v}_1}{(\sum x_i/v_i)(1-C^2{v}_1^2)}\left|\frac{\mathrm{\Delta }C}{C}\right|=\frac{x_1/v_i}{\sum x_i/v_i}{\tan }^2{\theta }_1\left|\frac{\mathrm{\Delta }C}{C}\right|$$

Which could skyrocket when

$\tan {\theta }_1\to y/x_1$.

The same thing occurs if

$T$ is in terms of

${\theta }_1$:

$$\frac{1}{C}\frac{\mathrm{d}C}{\mathrm{d}{\theta }_1}=\cot {\theta }_1$$
And thus

$$\left|\frac{\mathrm{\Delta }T}{T}\right|\gtrsim \frac{x_1/v_1}{\sum x_i/v_i}{\theta }_1\tan {\theta }_1\left|\frac{\mathrm{\Delta }{\theta }_1}{{\theta }_1}\right|$$

Which still wouldn't work when

$\sum x_i/v_i$ is small enough.

Now suppose

$T$ is terms of

$\tan {\theta }_1$.

$$\frac{1}{C}\frac{\mathrm{d}C}{\mathrm{d}\tan {\theta }_1}=\frac{1}{C{v}_1}{\cos }^3{\theta }_1=\frac{{\cos }^2{\theta }_1}{\tan {\theta }_1}$$
You could already see that the

$\cos$'s should cancel out the

$\tan$'s, with

$\sin$'s remaining, so that the reasoning above does not show that it skyrockets.
And indeed

$$\left|\frac{\mathrm{\Delta }T}{T}\right|\lesssim \frac{(\sum x_i/v_i\sqrt{1-C^2{v}_i^2})(C^2{v}_1^2/(1-C^2{v}_1^2))}{\sum x_i/v_i\sqrt{1-C^2{v}_i^2}}\left|\frac{\mathrm{\Delta }C}{C}\right|$$

$$\left|\frac{\mathrm{\Delta }T}{T}\right|\lesssim {\sin }^2{\theta }_1\left|\frac{\mathrm{\Delta }\tan {\theta }_1}{\tan {\theta }_1}\right|\le \left|\frac{\mathrm{\Delta }\tan {\theta }_1}{\tan {\theta }_1}\right|$$

Thus to obtain the answer with a relative precision of

${10}^{-9}$, it suffices to calculate

$\tan {\theta }_1$ to a relative precision of about

${10}^{-9}$.

Given

$X=\tan {\theta }_1$,

$C^2=\frac{X^2}{v_1^2(1+X^2)}$.

$T$ is then given by

$$T(C)=\sum \frac{x_i}{v_i\cos {\sin }^{-1}(C{v}_i)}=\sum \frac{x_i}{v_i\sqrt{1-C^2{v}_i^2}}$$

A potential culprit of numerical instablility is the subtraction, but by expanding the term,

$$1-C^2{v}_i^2=1-\frac{v_i^2{X}^2}{v_1^2(1+X^2)}=\frac{v_1^2+(v_1^2-v_i^2)X^2}{v_1^2+v_1^2{X}^2}$$
This can still be calculated presicely (as

$v_i$ are integers).

---

pH - 黑白雞

Author: toxicpie
Setter: toxicpie

題目：給

$N$ 顆雞蛋的顏色、被生下的時間以及美味程度，限制每兩次吃雞蛋要間隔

$K$ 秒，求在

$T$ 秒內吃恰好

$B$ 顆黑雞蛋和

$W$ 顆白雞蛋的最大美味程度總和。

Subtask 1

只要能吃到

$B$ 顆蛋，那答案就是

$B$，否則是

$-1$。因為每顆蛋都長一樣，所以在某個時間點如果有蛋可以吃，那先吃一顆不會虧。

$T\le {10}^{18}$ 的暴力模擬不會過，不過我們可以把雞蛋按照

$s$ 排序，然後重複做以下的事：

1. 令
   $time$ 為上次吃蛋的時間，一開始為
   $-\mathrm{\infty }$。
2. 每次選還沒吃的蛋當中
   $s$ 最小的，然後等到能吃它的最早時間
   $max(time+K,s)$ 時把它吃掉。

時間

$\mathcal{O}(N\log N)$

Subtask 2

對於任意的吃蛋方案，我們可以把所有吃蛋時間盡量往後推，變成在

$T,T-K,T-2K,\dots ,T-(B-1)K$ 時各吃一顆蛋（如果再晚的話會來不及吃完）。這時我們發現在每個時間點吃蛋時，如果沒有蛋可吃那答案是

$-1$，否則選擇目前美味程度最大的吃一定不虧。

把

$s_i$ 排序之後可以維護一個美味程度的 set 或 priority queue 來做事。

時間

$\mathcal{O}(N\log N)$

Subtask 3

解法一

假設有某種方法可以吃

$B$ 顆黑雞蛋和

$W$ 顆白雞蛋。考慮該方法，但每次吃蛋時，我們改為吃同樣顏色的蛋中生下時間最早的。到最後，我們吃的蛋的集合一定是

$s$ 最小的

$B$ 顆黑蛋和

$s$ 最小的

$W$ 顆白蛋。所以只考慮那些蛋，然後用 Subtask 1/2 的做法即可。

時間

$\mathcal{O}(N\log N)$

解法二

考慮 Subtask 2 的做法，但是分成兩個版本：

1. 當兩種顏色的蛋都有時，優先選擇黑色。假設此版本能吃到
   $B^{\prime }$ 顆黑蛋
2. 當兩種顏色的蛋都有時，優先選擇白色。假設此版本能吃到
   $W^{\prime }$ 顆白蛋

如果以上的答案都不是

$-1$ 且

$B^{\prime }\ge B,W^{\prime }\ge W$，那答案是

$B+W$，否則答案是

$-1$。
這邊用到的性質可以在下面的 Proofs 找到。

時間

$\mathcal{O}(N\log N)$

Subtask 2, 3 的順序和分數好像應該要互換？

Subtask 4

令

$f(x)$ 為總共吃

$B+W-x$ 顆黑雞蛋和

$x$ 顆白雞蛋時，美味程度總和的最大值。我們要求的是

$f(W)$。

如果

$f(W)$ 沒有定義，那答案就是

$-1$。
由 Subtask 3 可以知道，如果

$f(a)$ 和

$f(b)$ 都有定義，那

$\mathrm{\forall }a\le c\le b$，

$f(c)$ 都會有定義。也就是說，

$f$ 有定義的地方是某些連續的非負整數。

直接求

$f(W)$ 可能十分困難，但求

$f$ 的最大值很簡單 (Subtask 2)。如果

$f$ 在有定義的地方是凹函數，那可以用傳說中的 Aliens trick，也就是二分搜一個

$\lambda$ 滿足

$W=\arg \underset{x}{max}f(x)-\lambda x$，而此時的

$f(W)-\lambda W$ 即是答案。

$f(x)-\lambda x$ 的最小值求法就是把所有的白雞蛋美味程度加上

$\lambda$，然後做 Subtask 2。

時間

$\mathcal{O}(N\log N\log V)$，其中

$V$ 是美味程度的最大值。

Proofs

TBA

---

pI - 東門大地主

Author: erd1, HNO2
Setter: erd1

題目：給定一棵樹，每個點上面有水。每次詢問是戳一個點，所有點的水匯往該點走一步，並輸出點上原有的水量。

Subtask 1

暴力模擬。

$O(NQ)$。

Subtask 2

暴力模擬。只要遇到沒水的點就直接break掉。但是一開始水可能不聯通，所以這樣會 WA。你只要初始化時給每個人一個

${10}^{-9}$ 的水就好（或官解是拿pair<int, bool>）。

因為樹是隨機生成的，你去估計每個人的深度總和你會發現他是均攤

$O(N\log N)$ 的。

Subtask 3

拿 treap 暴力模擬。

$O((N+Q)\log N)$。

Subtask 4

先假設一開始的水都是連通的而且每次一定會戳出水來。有水的區域一定是一個連通塊

$T$。在子圖

$T$ 上對所有的鏈（一串度數至多

$2$ 的點）開一個 treap 維護。每次花

$O((x+y)\log n)$ 暴力 dfs 那個子圖（對每個鍊跟每個練的交會處暴力模擬），其中

$x$ 是所有（在

$T$ 上）的度數大於等於

$3$ 的點（鏈的交會處），而

$y$ 是所有（在

$T$ 上）的度數等於

$1$ 的點。鏈的個數顯然是

$O(x+y)$個的。注意到

$x=\mathrm{\Omega }(y)$ （因為每次分岔至少會多出一個葉子），因此每次暴力複雜度是

$O(y\log n)$。
又因為每次戳完，有水的點會減少

$\mathrm{\Omega }(y)$個（只有被戳的那個點即使是葉子也有可能留著）。因此均攤下來這樣是

$O(N\log N+Q\log N)$的。

一開始有沒水的點的處理方式與 Subtask 2 相同。

如果現在戳了沒水的點，有水的點只會至多多一個（

$T$的鄰居裡面離該點最近的點），因此以上複雜度估計還是好的。至於要找到最近的點的方法可以用 倍增法或樹壓平之類的。官解用的是 LCT。

Sidenote

這題根本暴力模擬題，唯一的難度就只有維護那個大便結構。出題者寫了三個小時的官解，加上中間受不了跑去休息的三個小時，以及寫完以後除了四個小時的蟲，總共花了十個小時。負責驗題的大概斷斷續續奮鬥了兩三天最後放棄了ＱＱ

---