嗯！

一眼交换前缀和，直接上无限序列，则环上一对 $i,j$ 的贡献好算。ds 优化。

嗯！

排序后从小到大贪心，维护 $b$ 的指针 $nw$。如果 $b_{nw}\le a_i+y$ 直接匹配，否则扔进待定队列。

但是贪心过程中要保证待定队列里的东西仍然有合法匹配！数据结构维护一下即可。

边定向，小度连大度，这样 $deg\le \sqrt m$ 的点出边不超过 $\sqrt m$，度数大的点后面至多 $O(\sqrt m)$ 个点，所以每个点出度不超过 $O(\sqrt m)$。

接下来对于每个点 $x$ 找出 $x$ 往后的三元环，枚举一条边再枚举一条边。如果 $(x,a,b)$ 是三元环那么连边 $(a,b)$，在新图用 bitset 数新图的三元环，就是从 $x$ 开始的 $K_4$。复杂度可以看成每个点至多连出去 $O(\sqrt m)$ 边所以 bitset 只要开这么大。原图三元环数目 $O(m\sqrt m)$ 级别，每条边 bitset 操作，复杂度是 $\frac {m^2} w$。太厉害了！

先忽略 $0$ 对

注意到一条路我来回走 $k$ 次对答案没有影响，这个意思就是我可以满图跑，随便选条边走两次或者找个环跑一遍。

然后就变成了 $k$ 进制线性基下面求最小 xor 了。要注意下这个东西的写法（和 $k$ 的 gcd 之类的东西）。

复杂度好像是 $O(n\log n \log k)$？

D1T1

shaber 题

D1T2

谁想得到啊？

D1T3

线性代数在 oi 中没有应用。

1. 下文 $c$ 为题面中的 $\lfloor \frac c 2\rfloor$，周长为短边和长边之和。
2. 短边边长不超过 $\sqrt s$
3. 添加 $1\times 1$ 的矩形你会发现 $2S-C$ 不变。

所以令 $f_i$ 为 $2S-C=i$ 时的最小 $C$，然后依次枚举短边长度，维护一个 dp：

1. 添加一个 $i\times i$ 的矩形：$f_{x-2i^2+2i}+2i\rightarrow dp_x$
2. 延长一个矩形，$dp_{x-2i+1}+1\rightarrow dp_x$
3. 更新 $f$

然后答案很好算。复杂度 $s\sqrt s$。