# IOICamp 2023
# Final
Editorial
---
## Problem A
騷擾選手的卷積
----
簡報上的粗體字應該有提醒大家想想看：
- FWT 的位元是獨立的嗎？
- FWT 的計算順序重要嗎？
----
思考後可以發現，對，每個位元是獨立的。
如果可以求得每一種位元卷積的變換，就可以這樣實作：
```cpp=
const int mat[2][6][2][2] = {
{ // transform matrix
{ // AND
{1, 1},
{0, 1}
},
},
{ // inverse transform matrix
// ...
}
};
void transform(const int N, std::vector<int>& A, const std::vector<int>& X, int inv = 0) {
for (int d = 0, k = 1, u, v; k < N; ++d, k <<= 1) {
for (int i = 0; i < N; i += 2 * k) {
for (int j = 0; j < k; ++j) {
u = A[i + j];
v = A[i+j+k];
A[i + j] = mad(mul(u, mat[inv][X[d]][0][0]), mul(v, mat[inv][X[d]][0][1]));
A[i+j+k] = mad(mul(u, mat[inv][X[d]][1][0]), mul(v, mat[inv][X[d]][1][1]));
}
}
}
}
```
----
那要怎麼求轉換矩陣呢？
- XOR 好好用線性代數算
- N$\oplus$ 就只是 $\oplus$ 算完之後兩半 swap ，所以把轉換或逆轉換其中一個矩陣的 row 交換就好了。
- 也可以用 `if (x[i] > 2) swap(u, v);` 做。
----
為什麼我的 XOR 卷積不會過？
- 逆矩陣要記得除以行列式值。
----
官解：
```cpp=
#include <bits/stdc++.h>
const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;
const int NEG1 = MOD - 1;
const int NEGINV2 = MOD - INV2;
inline int mad(int u, int v) {
u += v - MOD;
u += MOD & (u >> 31);
return u;
}
inline int mul(int u, int v) {
return (int) ((int64_t) u * v % MOD);
}
const int mat[2][6][2][2] = {
{ // transform matrix
{ // AND
{1, 1},
{0, 1}
},
{ // OR
{1, 0},
{1, 1}
},
{ // XOR
{1, 1},
{1, NEG1}
},
{ // NAND
{1, 1},
{0, 1}
},
{ // NOR
{1, 0},
{1, 1}
},
{ // NXOR
{1, 1},
{1, NEG1}
},
},
{ // inverse transform matrix
{ // AND
{1, NEG1},
{0, 1}
},
{ // OR
{1, 0},
{NEG1, 1}
},
{ // XOR
{INV2, INV2},
{INV2, NEGINV2}
},
{ // NAND
{0, 1},
{1, NEG1}
},
{ // NOR
{NEG1, 1},
{1, 0}
},
{ // NXOR
{INV2, NEGINV2},
{INV2, INV2}
},
}
};
void transform(const int N, std::vector<int>& A, const std::vector<int>& X, int inv = 0) {
for (int d = 0, k = 1, u, v; k < N; ++d, k <<= 1) {
for (int i = 0; i < N; i += 2 * k) {
for (int j = 0; j < k; ++j) {
u = A[i + j];
v = A[i+j+k];
A[i + j] = mad(mul(u, mat[inv][X[d]][0][0]), mul(v, mat[inv][X[d]][0][1]));
A[i+j+k] = mad(mul(u, mat[inv][X[d]][1][0]), mul(v, mat[inv][X[d]][1][1]));
}
}
}
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin.exceptions(std::cin.failbit);
int N, K;
std::cin >> N >> K;
std::vector<int> A(N), B(N), X(K);
for (int& i: A) std::cin >> i;
for (int& i: B) std::cin >> i;
for (int& i: X) std::cin >> i;
transform(N, A, X);
transform(N, B, X);
for (int i = 0; i < N; ++i)
A[i] = mul(A[i], B[i]);
transform(N, A, X, 1);
for (int i = 0; i < N; ++i)
std::cout << A[i] << " \n"[i == N-1];
return 0;
}
```
----
附上天才 Tester `nathanlee726` 的實作：
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 998244353;
int n, k;
vector<int> a, b, bt;
int madd(int a, int b){return (a + b >= mod? a + b - mod: a + b);}
int msub(int a, int b){return (a < b? a + mod - b: a - b);}
int mmul(int a, int b){return (int) ((ll) a * b % mod);}
int mpow(int a, int b){
if(b == 0) return 1;
if(b == 1) return (a % mod);
int tem = mpow(a, b / 2);
if(b & 1) return (int) (((((ll)tem * tem) %mod) * a) % mod);
else return (int) (((ll)tem * tem) % mod);
}
void FWT(vector<int>& v, int inv){
for(int i = 0; i < k; i++){
int ty = bt[i] % 3;
int dv = 0;
if(ty == 2) dv = mpow(2, mod - 2);
for(int j = 0; j < n; j += (1 << (i + 1)))
for(int l = j; l < j + (1 << i); l++){
int x = v[l], y = v[l + (1 << i)];
if(ty == 0){
if(inv) v[l] = msub(x, y);
else v[l] = madd(x, y);
}
if(ty == 1){
if(inv) v[l + (1 << i)] = msub(y, x);
else v[l + (1 << i)] = madd(x, y);
}
if(ty == 2){
if(inv) v[l] = mmul(madd(x, y), dv), v[l + (1 << i)] = mmul(msub(x, y), dv);
else v[l] = madd(x, y), v[l + (1 << i)] = msub(x, y);
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for(int i = 0; i < n; i++){int x; cin >> x; a.push_back(x);}
for(int i = 0; i < n; i++){int x; cin >> x; b.push_back(x);}
for(int i = 0; i < k; i++){int x; cin >> x; bt.push_back(x);}
FWT(a, 0);
FWT(b, 0);
for(int i = 0; i < n; i++) a[i] = mmul(a[i], b[i]);
FWT(a, 1);
int bse = 0;
for(int i = 0; i < k; i++) bse |= ((bt[i] >= 3) << i);
for(int i = 0; i < n; i++) cout << a[i ^ bse] << " \n"[i == n - 1];
return 0;
}
```
---
## Problem B
讓我們先加上一個條件：
每次蛋餅都會選擇序列 A，那要怎麼做呢？
----
合法的結果長怎麼樣？
假設 $Q$ 是 $A$ 的差分序列，那
1. $\sum{\max(0, Q_i)} \le K$
2. $\sum{Q_i} = 0$
----
於是我們可以令 $dp_{i,j,k}$ 代表長度為 $i$，正的和為 $j$，總和為 $k$ 的序列有幾種，列出轉移式後發現可以用前綴和優化加速到均攤 $O(1)$ 轉移。
----
但是每次蛋餅可以選擇 $A,B$ 序列之一要怎麼辦？
----
其實我們可以想像蛋餅最一開使都選擇 $A$ 序列，最後的時候再決定要把 $A$ 序列上面的值搬動多少給 $B$ 序列。所以我們在計算 $dp_{i,j,k}$ 時，直接再替 $dp_{i,j,k}$ 乘上 $k+1$ 即可
---
## Problem C
三口羊之戰
----
給你 $N$ 個點和 $M$ 條線段，這 $M$ 條線段互不相交，求有幾對點之間的連線不經過任何線段。
----
枚舉每一個點 $A$
這個點可以看到多少個點？
----
考慮以它出發的極角掃描線
當掃描線碰到一個點 $B$ 時
我們想知道 $A,B$ 之間是否有經過任何一條線段
----
每一條線段都會在一段時間內和掃描線相交
$A,B$ 之間有線段 <=> 掃描線上離 $A$ 最近的線段，和 $\overline{AB}$ 相交
----
用 `std::set` 維護與掃描線相交的線段
交點到 $A$ 的距離順序
怎麼排序？
----
一種無腦的方法是直接硬爆射線交點
接下來我們講一種全整數的作法
----
對於每一條線段 $\overline{P_1P_2}$
調整兩個點順序使得 $\overrightarrow{AP_1} \times \overrightarrow{AP_2} > 0$
----
比較兩條線段時
假設它們的兩個點依序是 $P_1,P_2$ 和 $P_3,P_4$
調整兩條線段的順序使得
$\overrightarrow{AP_1} \times \overrightarrow{AP_3} > 0$
----
<img src="https://i.imgur.com/xyUzAlg.png" width="400" />
----
- 它們一定會相交。
- 它們聯集起來不會是全部，因為一個線段的角度範圍會小於 $180^\circ$。
- 射線 $\overrightarrow{AP_3}$ 一定會通過兩條線段。
----
只要判斷 $\overline{AP_3}$ 是否和 $\overline{P_1P_2}$ 相交
是的話代表第一條線段比較近
----
另一種無腦的作法
是 $A$ 到那四個點的射線肯定有其中之一和兩條線段相交
射線和線段相交檢查 is left as an exercise
----
$O(N^2 \log N)$
Fun fact: 把 set 換成 vector 不會比 set 慢太多（`set::insert` = `vector::lower_bound` + `vector::insert`、`set::erase` = `vector::lower_bound` + `vector::erase`），不過除非你是壓常超人，不然應該不會過這題。
Not fun fact: 我昨天晚上 11:30 回家路上遇到三口羊
---
## Problem D
----
簡易題敘：把一個長度 $N$ 的正整數序列切成 $k$ 段，令第 $i$ 段結尾是 $p_i$，則需滿足 $l_{p_i}\leq p_{i-1}\leq r_{p_i}$。令每段的花費為區間最大值 $\times$ 長度，最小化每段花費的總和。
----
分治的上課例題？
- $dp[i] = \min_{\color{red}{l_i\leq j\leq r_i}}\{dp[j]+\left(\max_{j<k\leq i}a_k\right)\times(i-j)\}$
- 上課是 $1\leq j\leq i-C$
----
基本上做法都寫在投影片上了（？
- 不同的是要改把區間 $[l_i, r_i]$ 打到線段樹上
- 再次強調一下實作細節
- 記得用 sparse table 得出區間 $\max$
- 這題的斜率優化是用 stack 做單調斜率優化
- 這題的斜率會一樣，所以單調斜率優化的時候要特判斜率一樣取截距小的
----
標程
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000 + 1;
const int MAXN = 500005;
ll dp[MAXN];
int val[MAXN];
int mx[__lg(MAXN) + 1][MAXN];
vector<int> seg[MAXN << 2];
void add(int L, int R, int l, int r, int rt, int idx) {
if (L <= l && R >= r)
return seg[rt].push_back(idx);
int mid = (l + r) >> 1;
if (L <= mid) add(L, R, l, mid, rt << 1, idx);
if (R > mid) add(L, R, mid + 1, r, rt << 1 | 1, idx);
}
int get_mx(int l, int r) {
int lg = __lg(r - l + 1);
return max(mx[lg][l], mx[lg][r - (1 << lg) + 1]);
}
ll get_v(int tr, int idx) {
return dp[tr] + (ll)get_mx(tr + 1, idx) * (idx - tr);
}
void upd(int tr, int idx) {
dp[idx] = min(dp[idx], get_v(tr, idx));
}
void dfs(int l, int r, int rt) {
if (l == r) {
for (int idx : seg[rt])
upd(l, idx);
return;
}
int mid = (l + r) >> 1;
dfs(l, mid, rt << 1);
dfs(mid + 1, r, rt << 1 | 1);
val[r] = 0;
for (int i = r - 1; i >= l; --i)
val[i] = max(val[i + 1], mx[0][i + 1]);
for (int idx : seg[rt])
val[idx] = get_mx(r + 1, idx);
int nw;
vector<int> stk;
auto challenge = [](int a, int b, int c, auto f) {
auto [ma, ka] = f(a);
auto [mb, kb] = f(b);
auto [mc, kc] = f(c);
return (kb - ka) * (ma - mc) >= (kc - ka) * (ma - mb);
};
// m_x <= m_y
stk.clear();
nw = r;
auto f1 = [&](int i) {
return pair<ll, ll>(i, dp[i]);
};
for (int idx : seg[rt]) {
while (nw >= l && val[nw] <= val[idx]) {
while (int(stk.size()) >= 2 && challenge(stk[int(stk.size()) - 2], stk.back(), nw, f1))
stk.pop_back();
stk.push_back(nw);
--nw;
}
while (int(stk.size()) >= 2 && get_v(stk[int(stk.size()) - 2], idx) <= get_v(stk.back(), idx))
stk.pop_back();
if (!stk.empty()) upd(stk.back(), idx);
}
// m_x >= m_y
stk.clear();
reverse(seg[rt].begin(), seg[rt].end());
nw = l;
auto f2 = [&](int i) {
return pair<ll, ll>(val[i], dp[i] - (ll)i * val[i]);
};
for (int idx : seg[rt]) {
while (nw <= r && val[nw] >= val[idx]) {
// the slope may be the same in this case
if (!stk.empty() && val[stk.back()] == val[nw]) {
auto [m, k] = f2(stk.back());
auto [nm, nk] = f2(nw);
if (k >= nk) stk.pop_back();
else {
++nw;
continue;
}
}
while (int(stk.size()) >= 2 && challenge(stk[int(stk.size()) - 2], stk.back(), nw, f2))
stk.pop_back();
stk.push_back(nw);
++nw;
}
while (int(stk.size()) >= 2 && get_v(stk[int(stk.size()) - 2], idx) <= get_v(stk.back(), idx))
stk.pop_back();
if (!stk.empty()) upd(stk.back(), idx);
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, L;
cin >> n, L = __lg(n);
for (int i = 1; i <= n; ++i)
cin >> mx[0][i], dp[i] = INF;
for (int i = 1; i <= n; ++i) {
int l, r;
cin >> l >> r;
add(l, r, 0, n, 1, i);
}
for (int i = 1; i <= L; ++i)
for (int j = 1; j + (1 << i) <= n + 1; ++j)
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
dfs(0, n, 1);
cout << dp[n] << "\n";
}
```
----
$N$ 很小？
- 其實斜率優化那個部分可以直接動態凸包砸下去就收工了
- 有板子的話會好寫很多XD
---
## Problem E
----
$\dfrac{1}{p}+\dfrac{1}{q} = \dfrac{p+q}{pq}$
----
假設 $p\neq q$
$p+q$ 與 $pq$ 互質：
$p,q$ 皆為質數 $\implies$ $pq$ 的因數只有 $1,p,q,pq$
若 $p+q$ 為 $p$ 的倍數，則 $q$ 為 $p$ 的倍數（矛盾）
若 $p+q$ 為 $q$ 的倍數，則 $p$ 為 $q$ 的倍數（矛盾）
$\implies$ $p+q$ 與 $pq$ 互質
----
將 $\dfrac{a}{b}$ 約分至最簡分數 $\dfrac{a'}{b'}$
$\implies$ $p+q = a', pq = b'$
$\implies$ 想辦法求出 $p,q$
----
$\begin{cases}
p+q = a' \\
p-q = \sqrt{a'^2-4b'} \\
\end{cases}$
時間複雜度：$O(T\log{b})$
（求最大公因數）
----
走（一點點）自己的路：
* 記得約分
* $a'=b'=1 \implies p=q=2$
* $a'=2 \implies p=q=b'$
----
TLE 們：
* $O(T\sqrt{b})$（枚舉 $1$ 到 $\sqrt{b}$）
* $O(T\pi(b))$（枚舉質數）
* pollard rho（吃毒）
* Python（why ?_?）
---
## Problem F
滅台題（未定）
----
#### subtask 1
* 操作次數同於 $\texttt{AC}$ 的子序列數量
* $dp_{i, 0}$ 代表考慮前 $i$ 項的所有可能字串，$\texttt{AC}$ 的子序列總數量
* $dp_{i, 1}$ 代表 $\texttt{A}$ 的數量
* $dp_{i, 2}$ 代表有幾種可能的字串
* 轉移很好轉移
* 整體複雜度 $O(n)$
----
#### subtask 2
* 注意到當 $dp_i$ 轉移到 $dp_{i + 1}$ 的時候，轉移式同於一個 $3 \times 3$ 的矩陣
* 單點修改同於對一個轉移矩陣修改
* 開一棵線段樹支援單點修改
* 整體複雜度 $O(3^3(n + q\log n))$
----
#### 滿分解
* 想辦法在 dp 的過程維護出平方這種項
* 注意到在轉移的時候 $\texttt{AC}^2$ 這東西可以用 $\texttt{AC} \times \texttt{A}$ 和 $\texttt{A}^2$ 湊出來
* dp 需要維護更多東西！
----
* 以下都代表考慮前 $i$ 項的所有可能字串某個特定值的總和
* $dp_{i, 0}$ 代表 $\texttt{AC}^2$
* $dp_{i, 1}$ 代表 $\texttt{AC} \times \texttt{A}$
* $dp_{i, 2}$ 代表 $\texttt{A}^2$
* $dp_{i, 3}$ 代表 $\texttt{AC}$
* $dp_{i, 4}$ 代表 $\texttt{A}$
* $dp_{i, 5}$ 代表可能的字串數量
* 轉移可以用類似的想法推完
----
* 一些對於轉移有用的式子
* $\texttt{AC}^2 \to \texttt{AC}^2 + 2 \times \texttt{AC} \times \texttt{C} + \texttt{A}^2$
* $\texttt{AC} \times \texttt{A} \to \texttt{AC} \times \texttt{A} + (\texttt{A}^2 \ \text{or} \ \texttt{AC})$
* $\texttt{A}^2 \to \texttt{A}^2 + 2 \times \texttt{A} + \texttt{cnt}$
* $\texttt{AC} \to \texttt{AC} + \texttt{A}$
* $\texttt{A} = \texttt{A} + \texttt{cnt}$
----
* 轉移依然可以寫成一個 $6 \times 6$ 的矩陣
* 用類似 subtask 2 的想法用線段樹維護轉移式的矩陣
* 整體複雜度 $O(6^3(n + q \log n))$
---
## Problem G
----
構造一個長度為 $N$ 的序列，
使得其任意非空區間內的區間 XOR 都互不相同。
----
#### Subtask 1
* $N \leq 30$
* $a_i = 2^i$，好水
----
#### 觀察
* 簡化成前綴們的 XOR
* 令 $\displaystyle p_i = \bigoplus_{k = 1}^i a_k$
* $\displaystyle \bigoplus_{k = l}^{r} a_k = p_{l - 1} \oplus p_r$
* 找到 $\langle p_i\rangle_{i = 1}^N$ 使得 $p_x \oplus p_y$ 互不相同
----
#### Subtask 2
* Heuristic: 每次隨機抓一個合法的數加入序列
* 需要互不相同的集合：$\{p_x \oplus p_y\}$
* 新增之數不能在 $\{p_x \oplus p_y \oplus p_z\}$ 裡面
* 每次新增一數 $a_k$ 時，禁忌集合需要新增 $O(k^2)$ 項
* Overall: $O(N^3) \Rightarrow$ Subtask 2 Passed!
----
#### Alternative Solution
* 大大大隨機
* $\binom{400}{2} << 2^{30}$
----
#### Subtask 3
* 怎麼優化？照做！
* $5000^3 / 10^8 = 1250$ 秒
* 回頭看一下 code length 限制... 試試打表！
* 用 bitset 維護禁忌集合，每次取 mex 作為下一項
* Subtask 3 Passed!
---
## Problem H
----
一個極端區間是指兩端分別是兩個極值的區間，一個平衡排列是不存在任何極端區間使得長度不小於 3，給定 $N, K$ 求字典序第 $K$ 小長度為 $N$ 的平衡排列。
----
- 在算字典序之前應該要先知道這種序列的結構
----
- 在算字典序之前應該要先知道這種序列的結構
- 如果你是個快樂的打表人，你應該會發現恰有 $2^{N-1}$ 種排列
----
- 假設 $1$ 在最左邊，那只有唯一的排列 $1, N, 2, \ldots$
- 考慮固定 $1$ 的位置，每個其他的數字可以選擇在 $1$ 的左邊或右邊
- 固定之後排列就唯一了，因此個數是 $2^{N-1}$ 個
----
- 如果你是個懂觀察的打表人，你應該會發現恰有 ?? 種排列以 $M$ 開頭。
----
- 如果你是個懂觀察的打表人，你應該會發現恰有 $\binom{N-1}{M-1}$ 種排列以 $M$ 開頭。
- 組合對應、數學歸納法...
----
回顧前面，我們只要關心 $1$ 的左邊有誰即可，考慮一種從 $\{1, 2, \ldots, M - 1, M + 1, \ldots, N\}$ 選 $M-1$ 個數的方法。
不妨假設在 $\{1, 2, \ldots, M-1 \}$ 選到的是 $a_1 > a_2 > \ldots > a_k$, $\{M + 1, \ldots, N\}$ 中**沒有**選到的是 $b_1 < b_2 < \ldots < b_k$
那麼把這個選擇對應到排列
- $M, a_1, b_1, a_2, b_2, \ldots, a_k, b_k, 1, \ldots$, 若 $a_k \neq 1$
- $M, b_1, a_1, b_2, a_2, \ldots, b_k, a_k = 1, \ldots$, 若 $a_k = 1$
----
從上面的對應還可以知道 $p_1 = M$ 且 $p_2 > p_1$ 的排列數為 $\binom{N-2}{M-1}$, 否則為 $\binom{N-2}{M-2}$
- 也可以透過打表或通靈猜出這個結論（因為已知開頭為 $M$ 的個數形式所以其實是有可能直接猜到的）
----
直接逐項枚舉每一位應該要是多少，因為 $K \leq 10^{18}$，所以第一項一定不超過 $60$，這代表只要枚舉最多 $120$ 項就會跑到 $1$
- 實務上當 $N$ 夠大的話會更快因為 $\binom{N}{0} + \binom{N}{1} + \binom{N}{2} + \cdots$ 超快
- $N=10^6$ 底只會到 $3$, $N=1000$ 底只會到 $6$
----
除了前兩位以外，接下來每一位在枚舉的時候都會知道他應該要比前一樣大或小
e.x. $N=7$: $3, 5, x, ...$, 還剩下數字 $1, 2, 4, 6, 7$
$x=1$: $\binom{5-2}{1-1}=1$ 種 $(1, 7, 2, 6, 4)$
$x=2$: $\binom{5-2}{2-1}=3$ 種 $(2, 1, 7, 4, 6)$; $(2, 6, 1, 7, 4)$; $(2, 7, 1, 6, 4)$;
----
剩下的工作是快速計算組合數，但因為 $M$ 最多只會是 $60$，所以直接 $O(M)$ 計算即可。
複雜度沒有很重要，總之很快因為很多東西都比最差估計快很多。只要確保碰到 $1$ 就直接停下來把後面的數字一次性放進答案就好。
---
## Problem I
----
給定一個平面圖的平面鑲嵌，問他是幾-邊連通的（即刪掉幾條邊不連通）？
----
### Subtask 1:
- $n$ 很小，依據提示可以知道 $m$ 最多 $21$。直接枚舉所有 $2^m$ 種拔邊方式。
----
### Subtask 2:
$n \leq 60?$
- 考慮兩個點 $S$ 跟 $T$，要讓這兩個點不連通，發現答案就是 $S$ 到 $T$ 的 min cut，其中 capacity 都是 $1$。跑 $S$ 到 $T$ 的最大流就好了，注意邊是無向的。
----
- 因此只要枚舉所有 $S$ 跟 $T$，跑 $O(n^2)$ 次 dinic 就好了。
- 實際上這個問題叫做 global min cut，在帶權的情況下甚至存在 $O(n^3)$ 的算法，但通常都是抄板子，所以不預期有人這樣做。
- 另外，出題者出完才發現 IOIC 甚至沒教flow，所以這個 subtask 只是想讓剛好會 flow 的人有事情做，跟正解沒啥關係。
----
### Subtask 3:
答案只有 $0$ 跟 $1$。
- 你只要會判圖是不是連通的就好了，跟鑲嵌一點關係都沒有。
----
### Subtask 4:
答案還可以是 $2$。
- 如果圖沒有割邊（橋）答案就是 $2$，一次 dfs 解決，跟鑲嵌一點關係都沒有。
----
### Subtask 5:
答案還可以是$3$。
- ltf0501 曾經在台大 icpc 培訓班校內初選出過一般圖三連通分量。
- 神靈種 baluteshih(8BQube) 和唯一神 olmrgcsi(ckiseki) 都在賽中 AC 了，因此搞不好有人可以通靈出這題怎麼做。
----
- 其實 Radewoosh 也有發過線性四連通分量的論文。
- 但出題人當然不是希望你這樣做。出這個 subtask 是希望可以提示到答案總是很小，或是發掘跟上一頁提到的各種人物一樣的明日之星。正解請直接看下一個 subtask。
----
### Subtask 6:
本題實際上是一個拼裝車題。
- 首先從提示可以知道總是存在一個點的度數 $\leq 5$。只要把這個點的鄰邊都割掉就可以不連通，因此答案總是 $\leq 5$。
- 如何判 $0, 1, 2, 3, 4$？
----
- 再來是一個套路，考慮平板圖的對偶 (dual)，可以發現割和對偶圖的環是一一對應的。
- 實際上這是一個常見的技巧，但多半出現在一些比較規律 (例如grid) 的圖，比較常是$S-T$最小割轉最短路。
----
- 答案 $=0$：原圖不連通。
- 答案 $=1$：對偶圖上有**自環**。
- 答案 $=2$：對偶圖上有**重邊**。
- 答案 $=3$：對偶圖上有**三元環**。
- 答案 $=4$：對偶圖上有**四元環**。
- 除此以外答案是 $5$。
----
- 怎麼建造對偶圖？只要知道怎麼找出每一個面就可以了。
- 將每一個邊都拆成兩個方向，並規定一個面是逆（順）時針繞一圈。可以發現對於每一條邊 $u \rightarrow v$ ，只要能找到從 $v$ 盡可能左（右）轉是哪一條邊，就可以知道在（這個面上）這條邊的下一條邊是哪一條。
- 怎麼找？把出邊都極角排序！
----
```c++
vector<int> nxt(2 * m);
for (int i = 0; i < n; i++) {
auto &vec = g[i];
sort(vec.begin(), vec.end(), [&](auto x, auto y) {
return polarCmp(p[x.first] - p[i], p[y.first] - p[i]);
});
int sz = vec.size();
for (int i = 0; i < sz; i++) {
int j = (i + 1) % sz;
nxt[vec[j].second ^ 1] = vec[i].second;
}
}
```
----
```c++
int V = 0;
vector<int> id(2 * m, -1);
for (int i = 0; i < 2 * m; i++) {
if (id[i] == -1) {
for (int u = i; id[u] == -1; u = nxt[u])
id[u] = V;
}
V++;
}
}
vector<vector<int>> dual(V);
for (int i = 0; i < 2 * m; i++) {
dual[id[i]].push_back(id[i ^ 1]);
}
```
----
- 如何找三/四元環？事實上，**一般圖**三/四元環**計數**都可以在 $O(m \sqrt{m})$ 做到，只要寫得出這個就可以 AC 了。
- 具體作法有很多種，不過本質都差不多。因為網路上都有資料，以下只解釋三元環：
----
- 考慮將無向邊依照 $pair(deg[u], u)$ 小到大定向，得到一個dag。注意到每一個點的出度都不超過 $\sqrt{m}$ ，不然那個點就會超過 $\sqrt{m}$ 條出邊，且他指到的點的出度也都超過，就炸了。代碼如下：
```c++
for (int x = 0; x < n; x++) {
for (auto y : dag[x])
vis[y] = 1;
for (auto y : dag[x])
for (auto z : dag[y])
ans += vis[z];
for (auto y : dag[x])
vis[y] = 0;
}
```
----
四元環大概長這樣，但不解釋：
```c++
for (int x = 0; x < n; x++) {
for (auto y : dag[x])
for (auto z : g[y])
if (z != x) {
ans += vis[z]++;
for (auto y : dag[x])
for (auto z : g[y])
if (z != x) {
vis[z]--;
}
```
----
- 原本這題想要再出一個 $10$ 分左右的 subtask，$n \leq 1e6$，因為平面圖的三/四元環**計數**可以在**線性**時間內做到。這可能是本題唯一的精髓。
- 實際上，根號作法的核心就是定向後得到的 dag 的出度上界。能不能做得更好？
----
- 對於平面圖，因為總是有一個點度數 $\leq 5$，只要不斷把度數 $\leq 5$ 的點拔掉，並且每次拔一個點時將這個點僅剩的鄰邊都定向為出邊，就得到一個出度 $\leq 5$ 的有向無環圖。這可以用一個 bfs 實作。
- 套前面的做法就可以線性。
----
- 也存在別的作法。可以發現三元環或是四元環經過定向以後根本沒有幾種可能，直接判所 case 也行。（四元環的有一個 case 會用到 std::bitset 或是 std::set）
----
總結本題用到的東西
- 看提示，發現最小度數 $\leq 5$。
- 割轉環。
- 極角排序（用來建對偶圖）。$O(n\log n)$
- 三/四元環。$O(n)$，所有 $o(n^2)$ 其他做法應該都會過。
----
- 預期定位是hard。
- 但實作難度遠比 Day 5 定位習題的題目低！！！！！！
----
後記：
- 實際上，這題的測資偏弱。
- 整個 package 裡面都是一堆手畫 $+$ 手動輸入，$\leq 60$ 個點的圖。wolfram mathworld 的 planar graph 這因為出題人不會隨機產生大的 4/5-邊連通平面圖。所以大測資基本上都是不複雜的圖，或是一些其他比賽出過的平面圖題的測資，也因此沒有任何一筆 $\geq 100$ 個點的圖的答案是 $4$ 或 $5$，如果有人會做請教教我。
----
- 不知道有沒有人盲猜答案 $=$ 最小度數。
- 實際上這大部分時候是對的，出題人為了造最小度數從 $1$ 到 $5$ 的反例煞費苦心。對於最小度數是 $5$ 但答案是 $4$，出題人能造出的最小的圖有 $35$ 個點和 $96$ 條邊的 case，你能造出更小的嗎？
----
- 這兩個圖的拼接：
---
## Problem J
----
長度為 $N$ 的 LIS 其實就是要從某個 $1$ 開始依序經過 $2,3,\ldots$ 一直走到 $N$。
學長程度就是這東西的最小距離。
----
對於一個固定的排列，令 $i$ 出現在 $a_i$。
學長程度即為 $1+dist(a_1,a_2)+dist(a_2,a_3)+\cdots+dist(a_{N-1},a_N)$。
這裡 $dist(x,y)$ 是從位置 $x$ 向右走走到位置 $y$ 的最小距離。
----
把所有 $dist(x,y)$ 展開會發現等於 $a_N-a_1+1+\sum_{i=1}^{N-1} [a_i>a_{i+1}]\cdot N$。
因此我們可以考慮對每個 $i=1,2,\ldots,N-1$，去算有多少種排列滿足 $a_i>a_{i+1}$。
$a_N-a_1+1$ 的部分也是可以對 $1$ 和 $N$ 分開討論。
----
注意到要分成四種情況討論：($i$ 是否已經被固定) $\times$ ($i+1$ 是否已經被固定)
細節留給讀者自行思考。
----
注意到過程會用到階乘，所以顯然要先預處理。
總時間複雜度：$O(N)$
---
## Problem K
----
### Subtask 1
每條邊必須都要走到 -> 歐拉路
* 圖要連通：原題已經保證
* 奇偶性：令 $d_i$ 為第 $i$ 個點的度數，則 $d_1 \equiv d_n \equiv 1 \mod 2$ 且 $d_i \equiv 0 \mod 2\ (\forall\ 2 \le i \le n - 1)$
----
### Subtask 2
把題目想成「圖上已經有一些邊，加一些邊使得整張圖有 $1$ 到 $n$ 的歐拉路徑」
方便思考：加一條 $(1, n)$ 的重要路
題目就變成「加一些邊使得整張圖有*歐拉迴路*」
----
* 圖要連通：已經連通
* 奇偶性：圖上每個點有 $d_i$，對於每條非重要路 $(u, v)$ 你可以 $d_u+=1, d_v+=1$ 或不做，目的是把 $d_i$ 變偶數
----
現在圖上只剩非重要路
考慮生成森林，對於每個連通塊，可以用樹邊來 greedy 的取邊
如果小孩的 $d_i$ 是奇數就用連小孩的邊把它變偶數
----
greedy 過程很單純，不用構造解的話可以推到簡單結論
> 對於每一個連通塊，$d_u$ 是奇數的 $u$ 的數量都必須是偶數
先令 $d_1 = d_n = 1$，再分別把重要路的兩端都 $d_u += 1$，在只含非重要路的子圖上判斷這件事
$O(N + M)$
----
### 假解們
這題測資沒有很強qq
* 直接忽視有固定起終點
* 一開始加的是 $(1, n)$ 非重要路而不是重要路
* 含 DSU 的一些怪
* 其他怪又怪
---
## Problem L
----
- 題目大意
- $H$ 根據一張給定的圖 $H$，構一個圖 $G$ 使得
- $V(G)=V(H)$
- $E(G) = \{(u, v, w_i ) \mid \forall u,v\ \exists\ i \text{ s.t. }$
$D(H, u, u_i) \leq d_{1,i} \land D(H, v, v_i) \leq d_{2,i}\}$
- 求 $G$ 上的單點源最短路
----
### Subtask 1
- 樹退化成鍊的話怎麼做?
- 它就是個經典線段樹優化建圖練習題
- 可以把講義的建模稍微修改一下
- 複雜度 $O((N + Q) \log{N}\log{(N+Q)})$
----
### Subtask 2
- 回到樹的問題，能不能做類似的事情?
- 線段樹是把序列分治結果存下來，那樹有類似的方式嗎?
- 重心樹就是一種支援對樹上某個"區間"(距離某點特定範圍內的點們)做事的分治結構
----
- 重心樹優化建圖！
- 利用重心樹上"區間"們的關係，構造一個邊較少，但還是可以維持任兩點之間距離的新圖 $G$
----
- 重心樹上記錄這個所蘊含的"區間"內的每個點到它的距離
- 對每個重心樹節點 $u$ 建一系列 $G$ 上的點 $v_{u,i}$ 讓我們之後連到這個點就可以跟所有距離 $u$ 前 $i$ 近的點連
- 把"區間內"每個點都接到它對應的 $v_{u,i}$ 上，然後把 $v_{u,i}$ 串在一起
- Kinda similar to 前綴和思想 (?)
----
- 每次查詢一樣沿著重心樹往上走，在每個節點都查距離少於某個值對應到的 $v_{u,i}$ 是誰
- 這些 $v_{u,i}$ 就跟線段樹優化建圖時線段樹節點的功用一樣
----
- 建樹 $O(N \log^2{N})$
- 查樹 $O(Q \log^2{N})$
- **最後總共有 $O((N + Q)\log{N})$ 條邊與 $O(N\log{N} + Q)$ 個點**
- 帶入 Dijkstra 複雜度 $O(E \log{V})$ 中
- 總時間複雜度為 $(N + Q)\log{N}\log{(N\log{N} + Q)}$
---
## Problem M
----
水題。
---
{"metaMigratedAt":"2023-06-17T19:54:30.236Z","metaMigratedFrom":"YAML","title":"IOICamp 2023 Day 5 Contest Editorial","breaks":true,"contributors":"[{\"id\":\"791336ad-9906-4cf9-ae4f-8e2b6f9b856e\",\"add\":9444,\"del\":2713},{\"id\":\"8f3294cf-0a65-4b41-8b4d-80b1f6d5208a\",\"add\":5296,\"del\":2109},{\"id\":\"23e4e31a-87e4-4969-98c7-ac3a9c14f5a9\",\"add\":1253,\"del\":723},{\"id\":\"d7cc2e0a-f5c6-493c-baaa-f0efce285d9f\",\"add\":1579,\"del\":403},{\"id\":\"d14c47f5-9d89-4c85-8d7d-f5e2bc08cb62\",\"add\":515,\"del\":335},{\"id\":\"04d32f9a-57cc-45cd-8549-086ea8ee6d8a\",\"add\":5921,\"del\":1577},{\"id\":\"02353542-5acb-4a66-abd0-128b1af24abb\",\"add\":1100,\"del\":454},{\"id\":\"d3e63fe1-dc3b-4f31-97c0-10807543b008\",\"add\":1223,\"del\":9},{\"id\":\"d6f2ea40-6a64-4129-92e9-ea26e7b35ac5\",\"add\":719,\"del\":40},{\"id\":\"ae4b766f-b425-4139-98b1-cd8c8bbb7fb9\",\"add\":5091,\"del\":2324},{\"id\":\"6b95215f-91a7-4eaf-bcfe-d43740108f96\",\"add\":654,\"del\":1692},{\"id\":\"acb6534a-1dbb-4c0e-a5b9-1410fbceb21b\",\"add\":377,\"del\":0}]","description":"Editorial"}