## Final Scoreboard
## Statistics
### Problems Attempted/Solved
### Submissions Over Time
## Summary
基本上這場比賽被切成三個階段
- 前期題 CEFHI
- 中期題 BGML
- 後期題 AJK
- 不可做題 D（不是一個階段）
感覺大多數人前期題開完之後就被卡住了，可能是中期題過於 unusual 的關係 QQ
最正常的 G 似乎沒有人想到，但這題還算漂亮，推薦大家多想一陣子再看題解。
以下每題後面會附上我們預期的難度。
## Problem A. Area in Convex [mid-hard]
讓我們先考慮對於小凸包的一個頂點 $p$ 可以移動的範圍。
可以發現，對於每一條向量 $\overrightarrow{q_ip}$ 都會造成大凸包的每一條邊往內 $\overrightarrow{q_ip}$ 的限制，
其中 $q_i$ 是小凸包上的另一個點。
因此，對大凸包的每一條邊找到往內平移最多的 $\overrightarrow{q_ip}$，會是首要關鍵，而這除了用 $O(NM)$ 找到之外，也可以用雙指針類似[旋轉卡尺](https://oi-wiki.org/geometry/rotating-calipers/)的做法在 $O(N+M)$ 找到。實務上因為 $N, M\leq 10^4$，$O(NM)$ 的做法常數不要過大也可以很快找完。
找到大凸包的每一條邊平移的結果後，因為題目保證最終解存在兩個方向可以移動小凸包 => 該頂點可移動的範圍面積 $>0$，因此可以直接套用[半平面交](https://oi-wiki.org/geometry/half-plane/)來把範圍找出來，會是一個凸多邊形。這步可以 $O((N+M)\log(N+M))$ 搞定。
接著，我們希望用 $p$ 的移動範圍來還原出整個小凸包的覆蓋範圍，
注意到這其實是那些 $\overrightarrow{pq_i}$ 蒐集起來之後跟 $p$ 的移動範圍求[閔可夫斯基和](https://zh.wikipedia.org/zh-tw/%E9%96%94%E5%8F%AF%E5%A4%AB%E6%96%AF%E5%9F%BA%E5%92%8C)，因此可以在 $O((N+M)\log(N+M))$ 搞定。
但其實，半平面交和閔可夫斯基和的複雜度瓶頸都是排序，由於這題凸包的好性質，其實實作上可以完全避免排序，因此整題可以在 $O(N+M)$ 內完成。
比較值得注意的點是精度問題，原題保證了小凸包面積的 $10^5$ 倍不會小於最大座標絕對值的平方其實是在保證「太大的絕對誤差」不會造成精度上的困擾，但隨意實作還是很容易讓精度噴飛（ex. 過早將數字轉成浮點數後進行運算，如果之後還有乘法就可能放大誤差），在這種情況下，可以使用 `__float128` 來維持精度。
存在一份只用到 `double` 型態浮點數的解答。
## Problem B. Bogosort [mid]
### How to start with?
Let's think about a good scenario as ending --- the last $5$ consecutive numbers are repeatedly shuffled until all of them are correcly placed and once this is achieved, the array is sorted. If this is the case, we should have the other $95$ numbers correctly placed first.
### Heuristic Proposal
So, we may wonder if there exists any way such that after the $i$-th ($i \leq 95$) iteration, $a_j = j, \forall j = 1, 2, \ldots, i$. (And after that, just randomly shuffle $a[96..100]$ until $a$ gets sorted.) Good news: it's possible!
Based on the induction hypothesis (i.e. $[a_1, a_2, \ldots, a_{i - 1}] = [1, 2, \ldots, i - 1]$ before the $i$-th iteration begins), in the $i$-th iteration, let's do the following thing:
```
while True:
Shuffle a[i..N] // try our luck to hit a_i = i
/* Verify if you are that lucky */
record = []
Do C times: // C can be a constant
Shuffle a[(i + 1)..N]
append "the i-th smallest element of |a_z - z|" to record
if all the elements in record are zeros:
break // treat it as a sign of a_i = i
else:
continue // try again to make a_i = i next time
```
### Verification Validity
Let's see how the verification process can be valid.
#### False Negative
This does not happen. When $a_i = i$, the $i$ smallest $|a_z - z|$ must all be zeros because of the induction hypothesis. Hence, when we perform `? 1 i`, it always returns 0 if $a_i = i$.
#### False Positive
This **may happen** but with a low probability. A false positive occurs when both of the conditions below hold.
- $a_i \neq i$
- no [derangement](https://en.wikipedia.org/wiki/Derangement) happens in any of the $C$ shuffles
- Please note that this is an inaccurate statement since<br><br>$\{a_{i + 1}, a_{i + 2}, \ldots, N\} \neq \{i + 1, i + 2, \ldots, N\}$<br><br>when $a_i \neq i$. Anyway, you know what I mean.
The probability of the latter condition is upper-bounded by
$$
\left(1 - \dfrac{!n}{n!}\right)^C \approx \left(1 - \dfrac1e\right)^C \approx 0.632^C
$$
, where $n = N - i$ and $!n$ denotes the $n$-th derangement number. So, for sufficiently large $C$, the probability of the occurence of a false positive can be negligible.
### Implementation and Experiments
By taking $C = 30$ and an optimization --- conditionally "break" the "Do C times" loop if the number appended into the record is non-zero --- this heuristic method can succeed $995$ times out of $1000$ experiments. To make it even more robust, some trivial optimizations (e.g. dynamically determine $C$ depending on $i$ and the number of remaining queries, or rollback to a previous iteration if a suspicious false positive is detected with high confidence) can still be applied. But since there are only $20$ testcases, given the fact that $0.995^{20} > 90\%$, I would rather just submit my code again instaead of implementing more optimizations.
## Problem C. Communication Problem [easy]
As a contestant, you may first try on different $n$ to discover the pattern --- if you tried to do so, you were on the expected way to start with this problem.
As you may notice, except for the case where $k = n$, the answer is only determined by $k$. More specifically, when $k < n$, $ans_k = \dfrac{1}{k! + (k - 1)!}$.
This hypothesis seems arbitrary but you could find it reasonable after thinking twice. Let's consider the contribution when you add a number $x$ into the set $B$. The more divisors $x$ have, the larger the numerator is; however, $x$ grows much faster than $d(x)$, where $d(x)$ denotes the number of divisors $x$ have. In this case, adding a smaller number but keeping the nominator positive makes sense. More specifically, you may observe that for some small $n$,
$$
\begin{cases}
B_1 = \{2\}\\
B_k = B_{k - 1} \cup \{k + 1\}, \forall k = 2, 3, \ldots, n - 1\\
B_n = \{1, 2, \ldots, n\}
\end{cases}
$$
and this is the correct construction for all $n$ as well.
The explanation above may serve as an intuitive understanding instead of a rigorous proof. With this problem, we would like to introduce that finding the pattern before coming up with a claim is often useful and effective in competitive programming.
Since all the teams have solved this problem, let's omit the rigorous proof part and leave it as an exercise for you :)
## Problem D. Decision Problem [hard]
:::info
問題 D: 詢問樹上兩點間路徑有多少種數字出現偶數次。限定在線算法。
:::
### D.1 拆解問題
對於樹上路徑詢問的題目，通常可以先考慮序列（樹是一條鏈）的情形︰
:::info
問題 D.1: 給定一個序列 $a_1, a_2, \cdots, a_n$，$q$ 次詢問區間 $[l_i, r_i]$ 有多少種數字出現偶數次。
:::
這個問題可以輕易的使用[莫隊算法](https://oi-wiki.org/misc/mo-algo/)解決。注意到雖然[零是偶數](https://tw.news.yahoo.com/0%E7%82%BA%E4%BD%95%E6%98%AF-%E5%81%B6%E6%95%B8-%E5%B0%8F%E5%AD%B8%E7%94%9F-%E6%8B%9B%E5%91%8A%E8%A8%B4%E4%BD%A0-023035573.html)，但依據原題（D）題意，詢問範圍內沒出現過的數字不列入計算。因此問題 D.1 本質上是以下兩個子問題（D.1.1, D.1.3）的答案相減︰
:::info
問題 D.1.1: 給定一個序列 $a_1, a_2, \cdots, a_n$，$q$ 次詢問區間 $[l_i, r_i]$ 有多少種不同的數字。
:::
雖然也可以使用莫隊算法處理，但如果題目要求在線呢？
:::warning
練習 D.1.2（無關原題官解）: 在 $O((n + q)\log n)$ 的時間內解決問題 D.1.1。限定在線算法。
:::
:::info
問題 D.1.3: 給定一個序列 $a_1, a_2, \cdots, a_n$，$q$ 次詢問區間 $[l_i, r_i]$ 有多少種數字出現奇數次。
:::
與 D.1.1 不同的是，D.1.3 使用莫隊算法時不需要記錄每個數字實際出現的次數，只要記錄出現次數的奇偶性就好了。
對於莫隊算法能解決的問題，可以嘗試分塊。選擇常數 $k$，令集合 $S$ 為 $1 \sim n$ 中所有 $k$ 的倍數。對於所有 $p \in S$，紀錄每一種數字在 $[1, p]$ 中出現次數的奇偶性。由於整個序列至多有 $n$ 種數字，紀錄奇偶性需要 $O(n \cdot |S|) = O(n^2 / k)$ 的空間。
此外，對於所有 $p_1, p_2 \in S$，預先計算 $[p_1, p_2]$ 有多少種數字出現奇數次，需要 $O(|S|^2) = O(n^2 / k^2)$ 的空間。
至此預處理的步驟結束，時間和空間複雜度都是 $O(n^2 / k)$。
詢問時，令 $l^\prime_i = \max\left(k, l_i - (l_i \mod k)\right), r^\prime_i = \max\left(k, r_i - (r_i \mod k)\right)$，注意到 $l^\prime_i, r^\prime_i \in S$。
- 直接查表得知 $[l^\prime_i, r^\prime_i]$ 的答案。
- 一個數字在 $(l^\prime_i, r^\prime_i]$ 出現次數的奇偶性等於 $[1, r^\prime_i]$ 的奇偶性 XOR $[1, l^\prime_i]$ 的奇偶性。
- $\left|l_i - l^\prime_i\right| \le k$ 且 $\left|r_i - r^\prime_i\right| \le k$。
仿造莫隊算法移動區間的維護方式可以在 $O(k)$ 時間內回答一次詢問。
取 $k = O(\sqrt{n})$，即可得到時間複雜度 $O((n + q)\sqrt{n})$ 的演算法。結合 D.1.2 後問題 D.1 的在線版本也被解決了。
#### 觀察與結論
- 如果原題可以離線，似乎也能[在樹上使用莫隊算法](https://www.cnblogs.com/zwfymqz/p/9223425.html)？
- 可以用類似 D.1.3 的方法解決原題。
- 如 D.1.3，D 官解的空間複雜度也是 $O(n\sqrt{n})$。雖然這題並未特別限制記憶體用量，但這裡暗示了一個在空間上更有效率的作法︰如果儲存的資訊是 `bool` 而非 `int` ，用 `std::bitset` 實作只需要 $\frac{1}{32}$ 的儲存空間。
### D.2 樹上分塊
:::info
問題 D: 詢問樹上兩點 $u, v$ 間路徑有多少種數字出現偶數次。
:::
從暴力的作法開始發想︰分別從 $u, v$ 開始往上爬到 $lca(u, v)$，統計沿途數字的出現次數。這樣一次詢問需要 $O(n)$ 的計算時間。
如果能像 D.1.3 一樣找到集合 $S$ 使得 $u, v$ 往上爬不超過 $\sqrt{n}$ 次就會落在 $S$ 內，說不定就能在 $O(\sqrt{n})$ 的時間內回答詢問。
:::info
問題 D.2: 給定一棵 $n$ 個白點連成的有根樹和一個常數 $k$，將盡可能少的點塗黑，使得每個白點往根節點走至多 $k$ 條邊後能碰到黑點。
:::
用 greedy 解決 D.2︰
1. 按照後序考慮所有節點。
- 令當下考慮的節點為 $u$ 。若 $u$ 的子樹內存在白點 $v$ 滿足 $v$ 到 $u$ 的路徑上都是白點，且 $u, v$ 的距離恰好是 $k$，將 $v$ 塗黑。
2. 將根節點塗黑。
此時黑點的集合便是我們需要的 $S$，每個黑點代表樹上的一個「塊」，白點和往根節點走第一次碰到的黑點分在同一塊。
除了根節點外，每塗黑一個點至少會決定 $k$ 個白點的歸屬，因此 $S$ 的大小不超過 $\frac{n}{k} + 1$。這種分塊方式不能保證塊的大小，只確保每一塊的直徑不超過 $2k$。
### D.3 解決問題 D ... ?
:::info
問題 D: 給定一棵樹和點上的數字 $a_1, a_2, \cdots, a_n$，$q$ 次詢問樹上兩點 $u_i, v_i$ 間路徑有多少種數字出現偶數次。
:::
令 $1$ 為根節點。
D.3.1: 仿照 D.1.3 ，對於所有 $p \in S$，紀錄每一種數字在 $1$ 到 $p$ 路徑上出現次數的奇偶性。
D.3.2: 對於所有 $p_1, p_2 \in S$，預先計算 $[p_1, p_2]$ 有多少種數字出現**偶**數次（$0$ 不算在內）。作法是枚舉 $p_1$，令 $p_1$ 為新的根節點，跑一次 DFS 算出所有 $p_2$ 對應的答案。總花費時間是 $|S|$ 次 DFS = $O(n\sqrt{n})$。
D.3.3: 上面的 DFS 還有額外需要紀錄的東西︰對於 $1 \le i \le n$，$a_i$ 是否在 $p_1$ 走到 $i$ 的路上第一次出現。
令 $u^\prime_i, v^\prime_i$ 為 $u_i, v_i$ 對應的黑點，可以分成以下三種情況︰
#### Case 1: $u^\prime_i = v^\prime_i$
$u_i, v_i$ 屬於同塊，直接暴力算答案。
#### Case 2: $u^\prime_i, v^\prime_i$ 有一個是另一個的祖先
此時 $u_i, u^\prime_i, v^\prime_i, v_i$ 可能不會按順序形成一條鏈。
不失一般性假設 $v^\prime_i$ 是 $u^\prime_i$ 的祖先，將 $v^\prime_i$ 往 $u^\prime_i$ 方向退一個黑點。實作上可以預處理每個黑點往上走碰到的下個黑點，改由 $u^\prime_i$ 往上跳找出新的 $v^\prime_i$ ，花費時間取決於黑點數量 = $O(\sqrt{n})$。
此時 $u_i, u^\prime_i, v^\prime_i, v_i$ 按順序形成一條鏈，$v^\prime_i$ 不再是 $v_i$ 的祖先。
#### Case 3: 剩下的情況
此時 $u_i, u^\prime_i, v^\prime_i, v_i$ 按順序形成一條鏈，而且 $lca(u_i, v_i) = lca(u^\prime_i, v^\prime_i)$。
對於 Case 2, 3，分塊的性質保證 $u_i$ 到 $u^\prime_i$ 加上 $v^\prime_i$ 到 $v_i$ 的路徑長是 $O(\sqrt{n})$，因此我們可以暴力考慮這兩段路徑上的數字。
首先從 D.3.2 取得 $u^\prime_i$ 到 $v^\prime_i$ 的答案。
對於 $v^\prime_i$ 到 $v_i$ 的位置 $j$， D.3.3 在 $p_1 = u^\prime_i$ 的紀錄可以用來回答 $a_j$ 是否未曾在 $u^\prime_i$ 到 $v^\prime_i$ 出現。$u^\prime_i$ 到 $u_i$ 同理。
將 D.3.1 對於 $u^\prime_i$ 和 $v^\prime_i$ 的紀錄進行 XOR 運算可以得到數字在 $u^\prime_i, v^\prime_i$ 路徑上出現次數的奇偶性。記得將 $lca(u^\prime_i, v^\prime_i)$ （不是 $lca(u_i, v_i)$）的影響加回。
仔細算一下奇偶性，將新數字和 $u^\prime_i, v^\prime_i$ 路徑上本來就有的數字分開處理，這題就被我們解決了！時間複雜度是 $O((n+q)\sqrt{n})$，空間複雜度是 $O(n\sqrt{n})$。
### D.4 快取優化
不過事情其實還沒結束，當你終於寫完上面的做法，上傳後很可能會拿到一個 TLE。時間複雜度終究只表示了漸進行為，並未考慮 $(n+q)\sqrt{n}$ 前面的常數。須知 ~~NCPC 賽中 O(n^3 / w) 在 n = 1e4 時可以 1 秒內跑完~~ 在快取的影響下，循序存取會比隨機存取來的有效率，這也是樹和序列的一大差異︰序列上的分塊（或莫隊），移動區間時存取的索引總是連續的，而樹上移動時碰到的點編號毫無規律。
我們希望找到一種對點重新編號的方式使得 $u_i, v_i$ 往上移動的過程中碰到的點編號盡可能連續︰利用[樹鏈剖分](https://oi-wiki.org/graph/hld/)，對於同一條鏈上的點分配連續的編號，可以保證往上移動時至多經過 $O(\log n)$ 個連續區間。
D.4 的優化在出題者電腦上對時間的影響約為 3 倍。
## Problem E. Er Wei Shu Dian [water]
注意到這題問了總和。
如果座標的 $x$ 和 $y$ 全部相異，那任一對點對都會貢獻進總和裡（$y$ 比較小的會算到）
因此考慮從 $C^N_2$ 開始扣，$x$ 座標一樣的 $k$ 個點會多算到 $C^k_2$ 次、$y$ 座標一樣的也是，最後要把重合的點多扣的量加回來。
整體複雜度就是計算座標相同點的時間，這部分我們用 `std::map` 實作 $O(N\log N)$ 的解答可以在賽中用 0.31s 跑完，但好像有人還是被卡常了，我們很抱歉 QQ
## Problem F. Fake Solution [easy]
對於一個操作 $(a_i,j)$，如果原本 $a_i$ 第 $j$ 個 bit 是 1，那麼不會有任何影響；否則會把 $j$ 直到 $j$ 以上的第一個 1 以前的 0 都變成 1。
因此我們可以知道答案一定是 $2^p - 1$ 其中 $p$ 是所有 $a_i$ 當中最高位最大值。
接著要計算所需要的步數，我們先計算出原本的 bitwise-or 跟最好的答案差了哪些 bit，然後我們的目標就是用一些操作讓這些 bit 被蓋住，我們一次操作可以蓋掉的目標就是一個 $a_i$ 的二進位表示的一段連續 0 所對應的區間。選擇一些區間使得所有給定點都被至少一個區間覆蓋是一個經典貪心或動態規劃問題，其中一個作法是從可以蓋住最左邊的點的區間當中每次選右界最大的。
小心不要寫成 1e6 * 30^2 應該就會過了。
## Problem G. Grouping Problem [mid]
首先注意到要分組的話，肯定是座標排序後連續的人會在同一組，所以所有組別會對應到若干個互斥的連續區間。
如果 $a\leq b$，可以注意到不把任何人分在同一組肯定是最好的，所以 $b$ 變得無用了，這其實退化了成一個很單純的最小割問題（留給讀者自行練習）。
以下假設 $a>b$。
考慮最小割，如果值域很小的話，對每個「座標」都開一個點「座標 $x$」，也對每個人都開一個點「人 $x$」，表示這個人所在的位置是 $x$。考慮分在 $S$ 的點代表不選，分在 $T$ 的點代表要選，其中
- 「座標 $x$」選的意義是「存在一個組別的區間 $[l, r]$」滿足 $l \leq x \leq r$
- 「人」選的意義是這個人沒有被請走
那麼有以下限制：
1. 選了在座標 $x$ 的人，imply 座標 $x$ 要選
- 也就是 座標 $x$ -> 人 $x$，cost 無限大
2. 不選一個人，cost $c_i$
- 也就是 人 $x$ -> $T$，cost $c_i$
3. 選了一個座標，就等價可能貢獻了 $b$（但連續選座標的區間會多算一個 $b$，下一步解決）
- 也就是 $S$ -> 座標 $x$，cost $b$
4. 選了座標 $x$，卻不選 $x-1$ => 出現了一個區間的開頭
- 也就是 座標 $x-1$ -> 座標 $x$，cost $a-b$（抵銷一個 $b$，增加 $a$），注意到 $a>b$ 所以這是正的 cost
5. 人與人之間的朋友邊
- 也就是 $u_i$ <-> $v_i$，cost $w_i$ 的雙向邊
直接跑上圖的 $S-T$ 最小割，就會是答案。
注意到以上模型可能會生出「區間邊界沒有人」的區間，但這樣答案肯定只會更差，所以不用在意這件事。
那值域很大要怎麼做？其實可以把人與人之間的座標壓成一個點，cost 就是 $b$ 乘上長度，因為這段區間不可能有些座標選了有些座標不選，否則答案只會更差，因此總共就只有 $2 + N + 2N - 1 = 3N + 1$ 個點，邊量也是 $O(N+M)$，總共的時間複雜度若使用 [Dinic](https://zh.wikipedia.org/zh-tw/%E8%BF%AA%E5%B0%BC%E8%8C%A8%E7%AE%97%E6%B3%95) 演算法即為 $O(N^2(N+M))$。
一個容易踩到的錯誤是不把人跟座標分開建點，這樣會導致被蓋住的人被強迫選進來，但實際上可能會因為朋友邊的影響讓這個人被請走比較好，以下是一個手構發生這件事的測資，供參考：
```
4 1 3 1
1 2 3 100
9 1 9 1
2 4 5
```
## Problem H. Harmony Coloring [easy-mid]
先固定 $H$ 塗紅色，最後再把答案乘以 2。
分為兩個 case：
1. $T$ 一樣塗紅色。考慮藍色的點怎麼選，在拔掉 H 和 T 之後，整張圖只剩下一些鍊，因此藍色點只能選擇這些鍊的其中一個鍊上的一個區間。
假設選了 stem chain 則只能是一個前綴，而且剩下的紅色一定會連通，數量有 $S$ 個。
假設選了 stripe chain，則數量是 $\sum \frac{1}{2} l_i (l_i+1)$ 個。注意 $N = 1$ 的 case，因為拔掉那些藍色點之後剩下的紅色點必須要連通。
2. $T$ 塗藍色。這樣 stem chain 就一定整個都要是紅色。對於每個 stripe chain，我們都可以任意獨立的決定一個紅藍的分割點，因此這部份的答案是 $\prod (l_i + 1)$。
## Problem I. IMO Problem [easy]
> 據說 2022 TOI 二模出了一題 IMO 的複製題，我們怎麼可以出一樣的題目呢？所以這是那題的 checker。
把斜向左下和斜向右下分別訂成 $x$ 軸正向和 $y$ 軸正向，可以發現每次走到新一排的兩個圓就等於是從 $(x,y)$ 走到 $(x+1,y)$ 或 $(x,y+1)$。因此定好座標之後，就等於是要選一堆紅色圓使得他們的座標兩維都不嚴格遞增，等價於一個 LIS 問題之類的，可能也可以用資料結構做。
第 $i$ 橫排的第 $a_i$ 個紅色圓對應到上述的座標應該就是 $(a_i,i-a_i)$ 之類的。
## Problem J. Japanese Monsters [mid-hard]
**原本的解**
定義們：
* $N = |S|$
* $\text{Suf}_i = S_{i\dots N}$
* 若一個字串 $S$ 形如 $AA$，其中 $A$ 是某個非空字串，則我們稱 $S$ 是一個串串
* $\text{LCP}(A, B)$ 代表 $A$ 跟 $B$ 的最長共同前綴
題目要我們對每個 $i$ 算有多少種方式把 $\text{Suf}_i$ 拆成 $AABA$ 的形式，其中 $A$, $B$ 都是非空字串。
考慮枚舉結尾的 $A$，我們知道只要 $i+3|A| \leq N$，且 $\text{LCP}(\text{Suf}_i, A) = A$，且 $\text{Suf}_i$ 的前 $2|A|$ 個字元剛好是一個串串的話，那 $A$ 就會對 $i$ 貢獻 1。
想到串串就會想到 [Main-Lorentz](https://cp-algorithms.com/string/main_lorentz.html)，他可以對於每個 $2k$ 找到有哪些 $i$ 對應的 $S_{i \dots i+2k-1}$ 是一個串串，並且這些開頭們會形成一些區間，而總區間數量是 $O(N \log N)$。
注意到對於 Main-Lorentz 找出的區間，我們可以稍作調整，使得這些開頭也會符合 $i+3|A| \leq N$。
接下來我們剩下要做的事情就是確保 $\text{LCP}$ 是對的，這部分可以想像一棵[後綴樹](https://cp-algorithms.com/string/suffix-tree-ukkonen.html)。
我們知道後綴樹上 $u$ 的後代節點 $v$ 們跟 $u$ 所代表的 $\text{Suf}_u$ 的 $\text{LCP}$ 都是 $\text{Suf}_u$，所以若是 $\text{Suf}_v$ 的前 $2|\text{Suf}_u|$ 字元又剛好是個合法串串，那 $u$ 就會對 $v$ 貢獻 1。
綜合起來我們可以例如帶著 [Fenwick Tree](https://cp-algorithms.com/data_structures/fenwick.html) 去 dfs 後綴樹 (實作上可以用[後綴陣列](https://cp-algorithms.com/string/suffix-array.html)取代後綴樹)，每次走到 $u$ 的時候就把 Main-Lorentz 給我們的那些 $2|\text{Suf}_u|$ 對應的合法串串區間拿出來區間加值一下，離開 $u$ 的時候再撤銷，然後也順便檢查一下 $u$ 目前被貢獻多少了，這個值就是 $A_u$。
最花費時間的計算步驟是用 Main-Lorentz 給出的 $O(N \log N)$ 個區間，每個都拿去 BIT 作區間加值，因此總時間複雜度為 $O(N \log^2 N)$。
**更好的解**
出題的人看了 AYDD 的 submission 才發現其實可以 $O(N \log N)$ 😭
作法一樣枚舉結尾的 $A$，我們一樣要找開頭是 $AA$ 的後綴們，找到後 $A$ 就會對對這之中實際開頭在 $N - 3|A|$ 前的人貢獻 1。
明顯的這些開頭是 $AA$ 的後綴們會在後綴陣列上形成一個連續區間，而若是我們能定位出這個區間，那剩下的就是一個二維數點問題。
因此我們先來看該怎麼定位出這個區間。
一種做法是直接二分搜第一個開頭字典序 $\geq AA$ 的後綴是誰，接著再二分搜一次找到是 $AA$ 開頭的最後面的後綴是誰。
要檢查某個後綴 $U$ 是不是 $\geq AA$，我們可以先看 $U$ 在後綴陣列上的位置是不是比 $A$ 前面，若是的話他就一定不會 $\geq AA$；接著看 $\text{LCP}(A, U)$，若不是 $A$ 的話，因為我們知道 $U \geq A$，所以 $U > A \implies U > AA$；現在我們有 $\text{LCP}(A, U)=A$，所以剩下只要看是不是 $U_{|A|+1\dots|U|} \geq A$，等價的意思就是 $U_{|A|+1\dots|U|}$ 是不是在後綴陣列上比 $A$ 還後面 ($U$ 是 $S$ 的後綴，所以 $U$ 的後綴也會是 $S$ 的後綴，所以 $U$ 的後綴也都會出現在 $S$ 的後綴陣列裡)。
確定 $V$ 是不是 $AA$ 的情況也類似，只要檢查 $\text{LCP}(A, V)=A$ 且 $\text{LCP}(A, V_{|A|+1 \dots |V|})=A$ 即可。
所以最後剩下的問題就變成在一個序列(後綴陣列的逆元)上，有一些操作 $(L, R, v)$，代表要把位置介在 $[L, R]$ 且值少於 $v$ 的那些地方都 $+1$，這可以例如對操作們按 $v$ 由小到大排序，每次就變成是一些區間加值的操作了，一樣可以用個 Fenwick Tree 搞定。
計算量最大的部分在於二分搜跟 Fenwick Tree 操作，兩種的總複雜度都是 $O(N \log N)$ 的 (後綴陣列跟LCP都有$O(N)$的演算法)
## Problem K. Known Problem [hard]
考慮離線回答，對所有詢問的 $r$ 排序，$r$ 從小到大，每次加一個 $r$ 進來後更新所有 $l$ 的答案。
我們可以建立 $\log(C)+1$ 個資料結構，其中 $C$ 是值域、第 $i$ 個資料結構會保持到所有「有用的」距離介在 $(2^{i-1}, 2^{i + 1}]$ 的數對。特別地，第 $0$ 個資料結構維護的區間是 $[0, 1]$。
對於第 $i$ 個資料結構，我們將值域每 $2^i$ 個切成一塊，每個點 $x_r$ 在被加進來時會進到 $\lfloor\frac{x_r}{2^i}\rfloor$ 這塊裡面，接著他就暴力跟 $\lfloor\frac{x_r}{2^i}\rfloor-1$、$\lfloor\frac{x_r}{2^i}\rfloor$、$\lfloor\frac{x_r}{2^i}\rfloor+1$ 這三塊裡面的所有點建立出數對，假設建立出 $x_l, x_r$ 這個數對，那這兩個點就可以貢獻給所有未來詢問左界 $\leq l$ 的詢問。
接著，當一塊加入點之後超過 $3$ 個點，我們就可以移除這塊裡面 index 最小的點，如此一來整體的複雜度就會是 $N\log Cf(N)$，其中 $f(N)$ 是貢獻一個數對的時間，這裡可以用一個 BIT 維護，所以是 $N\log C\log N$，而每個詢問就是一個 BIT 查詢，總時間複雜度就是 $O(N\log C\log N + Q\log N)$。
那為什麼這樣就可以維護好次近數對呢？首先對於第 $i$ 個資料結構
:::info
當一塊裡面有超過 $3$ 個點後，肯定存在超過兩個 pair 的距離不超過 $2^{i-1}$
:::
所以，可以想像被 pop 掉 index 最小如果在這塊是「有用的」話，那他製造出來這個介在 $(2^{i-1}, 2^{i + 1}]$ 的距離肯定會被不超過 $2^{i-1}$ 的某個兩個數對在未來蓋住，因此他是沒有用的，pop 掉不影響解答。
這招可以用來做[區間最近點對](https://codeforces.com/gym/104172/problem/I)，但常數非常之大；而這題看起來存在原本 well-known 最近數對作法的延伸解（賽中過的隊伍好像都是這樣做），但出題者太信任 2017 這題的提出者所以以為這個做法不能做（Ｘ
## Problem L. List of Order [easy]
這題是在致敬 2022 ICPC 桃園站的閱讀測驗。
如果把 work 當成一個點，那可以建出一張 DAG，邊來自以下：
1. 每個 order 的順序
2. 同一個 item 的 work 對 dealine 排序
3. 每個 resource 的順序
接著，因為要移除某個 resource 的區間，所以這個區間在 resource 上左右的邊可以直接不建，並在空隙之間插入一條邊。
如此一來，原題變成
:::info
給定 DAG 上的兩個點 $s, t$，保證 $s$ 能走到 $t$，接著 $Q$ 筆詢問獨立加入 $(x, s)$ 和 $(t, y)$ 兩條邊後，是否會出現環。
保證每次詢問時都有一個 $(x, y)$ 的邊
:::
而因為 $s$ 能走到 $t$、$x$ 能走到 $y$，所以其實只要判 $(x, s)$ 和 $(t, y)$ 有沒有環就好了，也就是預處理 $s$ 能不能走到 $x$ 和 $y$ 能不能走到 $t$，這可以線性預處理。
整體複雜度就是在建圖之後成線性，至於建圖就算用 map 亂建也不會爆常數。
這題的難度全在文章，出題者也弄到快暴斃了，但大家絕對不能忽視閱讀通靈題敘的重要性，桃園站教育了我們。
## Problem M. More Japanese Monsters [mid]
**簡單的解**
這題雖然範圍比 J 大，但輸出總和的方式大大降低了這題的難度，所以有人開掉 M 沒開出 J 是非常預料之中的。
我們可以先將字串反過來後，計算 [Z-value](https://oi-wiki.org/string/z-func/) 後得到 $z_i$，接著算 ABAA 的數量。
試著窮舉第二個 A 的開頭，假設是 $i$，那就是問 $(i, i + \min(z_i, i - 1)]$ (0-based) 之間有多少 $j$ 滿足 $z_j \geq j-i \Rightarrow i \geq j - z_j$
考慮一個合法數對 $(i, j)$，其實他的貢獻是 $114514^{n+i-2j}$ ，所以只要對 $j-z_j$ 排序，窮舉到 $i$ 時已經被算過的 $j$ 都有 $i \geq j-z_j$，這時候只要查詢已經被算過的 $j$ 中 $114514^{-2j}$ 的區間和，就可以乘上 $114514^{n+i}$ 來得到 $i$ 的貢獻，可以用一個 BIT 搞定。
總時間複雜度 $O(N\log N)$。
**套 $O(N \log N)$ 的 J 的解**
這題的記憶體限制有一點緊，如果有人因為 LCP 開到 $O(N \log N)$ 的記憶體的話，可以注意到我們用到 $\text{LCP}$ 的部分其實都是在檢查 $\text{LCP}(X, Y)$ 跟 $X$ 是不是相等，所以可以例如直接改用 Hash 就可以有 $O(N)$ 空間的演算法了。
不過雖然是 $O(N \log N)$，但是這麼做常數相較前面簡單的做法可能大非常多，所以高機率要壓常😶
## Random Facts
- Problem C 源於真事，但因為事主是 -1e11，拿他當主角的話會暗示它是打表題，所以 YP 就上來當代罪羊了。
- Problem E 的來源是 rgnerdplayer 表示他不會做任何在二維平面上數點對（他稱二維數點）的操作，所以出題群決定出一題相關的題目制裁他，結果他首殺。
- Problem F 的來源是出題者在打某一場比賽時看錯題目（看成 version1），寫完之後還過範測，上傳之後 WA 成白痴才發現自己看錯。後來想出成題目之後發現自己又假解了，就硬把題目改大家賽中看到的樣子（version2, current version）。
- Problem G 的來源是出題者團練時不會做的題目，在嘗試把最小割 append 原題時覺得很美麗，卻發現原題的限制讓最小割行不通，結果最終解答也跟最小割一點關係都沒有，所以就暴力改限制變成現在的題目了。
- Problem H 的來源是 IOI 2022 國手們發明的「西瓜圖」，但其實出題群沒有任何 IOI 2022 國手，我們感謝國手們提供靈感。
- Problem J 是臨時被加進來的題目，原本只有 Problem M，但比賽前一陣子負責的出題者就表示他可以輸出所有對於每一個後綴都輸出，但大家實在是太忙了就沒有幫他想能不能更簡單。
- Problem K 其實可以把資料結構改成 $\langle O(1), O(\sqrt{N})\rangle$，進而讓複雜度變成 $O(N\log C + Q\sqrt{N})$，但 $N$ 那邊的常數真的很大，如果這樣出的話時限會被調到非常大，不然有通過的隊伍的做法其實都可以被卡掉（Ｘ
- Problem L 實際上是一個現實存在的問題，題目來源來自某一位退役選手的工作需求。
Sign in with Wallet
Connect another wallet