2023/12/06(#5)：收集着破碎的时间碎片

答案是，什么时候？

呼吸ひとつ生きる生きる
深吸一口气想着活下去

優しい日々の横で泣かぬように
都是为了不在美好的日子里在你身旁哭泣啊

愛をひとつまたねまたね
让我们再相爱一次吧

[AGC052D] Equal LIS

设 LIS 长度为 $m$ 。如果 $m$ 是偶数，那么对于 $f_i\le \frac m 2$ 。划分到一组，剩下的划分到另一组即可。

$m$ 为奇数时，我们只需要找到两个长度为 $\left\lceil \frac m 2 \right\rceil$ 的 IS 即可，构造时同样可以直接划分。具体来说，如果存在比 $m$ 多的可以成为 LIS 的点，那么直接划分，当 LIS 试图变得比 $\left\lceil \frac m 2 \right\rceil$ 大时直接扔到另一个序列即可。代码。

[AGC055C] Weird LIS

Portal.

设 $p$ 的 LIS 长度为 $K$ ，那么应该有 $a_i\in [K,K-1]$ 。我们将 $a_i\leftarrow a_i-K$ 。

排列上的数可以划分成四种类型：

让红黑匹配尽可能地先出现，那么 $f_{i,k}$ 代表以颜色 $i$ 为结尾，当前 $K=k$ ，直接做即可。代码。

[CF895C] Square Subsets

Portal.

~~只会做水题。~~

其实相当于是在求异或和为 $0$ 的数的个数，直接线性基，然后答案是线性基内数的个数。代码。

[CF1517F] Reunion

Portal.

设一种方案 $S$ 的半径为 $f(S)$ ，那么答案是 $\sum_{r=1}^{n}\sum_{S}[f(S)\ge r]$ 。实际上我们只需要对于每个 $r$ 分别计算即可。

设 $f_{i,j}$ 代表 $i$ 的子树距离 $i$ 最近的黑点距离为 $j$ 的方案数，记满足 $j=r+1$ 的为预备点， $g_{i,j}$ 表示 $i$ 子树内最深预备点与 $i$ 距离为 $j$ 时的方案数。

值得注意的是，若子树内已经存在预备点，那么没有必要再考虑距离 $i$ 最近的黑点与 $i$ 的距离。不存在时，这东西才需要被记录。

考虑使用树形背包的方式合并：

合并 $f_{x,i},f_{y,j}$ ，可以转移到 $f_{x,\min \{i,j+1\}}$ ；
合并 $g_{x,i},g_{y,j}$ ，可以转移到 $g_{x,\max\{j,k+1\}}$ ；
合并 $f_{x,i},g_{y,j}$ ，如果 $i+j+1>r$ ，那么 $g$ 定义的预备点是符合限制的，其会转移到 $g_{x,j+1}$ ，否则会转移到 $f_{x,i}$ ；
合并 $g_{x,i},f_{y,j}$ 大致同理。