题解：AT_arc138_f [ARC138F] KD Tree

· · 题解

我们考虑一个 dp：定义 dp_S 表示对 S 做分割的方案数，则显然边界条件为 |S|\le 1，此时 dp_S=1，答案为 dp_U。

尝试找到一个转移方式：可以枚举先怎么切一刀，然后把点集分成两份，递归查询即可。但显然会记重——因为不同的切法可能会把序列划分成同样的。所以我们考虑对于可以交换的分割线，定义分割线的顺序，那么我们对于所有本质相同的切法就可以只关注字典序最小的。

在确定当前集合以后，我们可以定义顺序为 x_1,y_1,x_2,y_2,x_3,y_3...x_k,y_k，x_i 和 y_i。定义 T_i 为按第 i 个切割线分出去（小于等于）的集合。我们定义求 S 集合的分割方案先切第 i 刀时 T_i 的分割方案有 f_i 种。先假设第一刀是按 x_i 分割的，则若有一刀 x_j（j<i），则有 f_{x_j}dp_{T_{x_i}\setminus T_{x_j}}dp_{S\setminus T_{x_i}} 这么多的方案是重复的，即 x_i 与 x_j 之间任意切，x_i 右侧任意切，显然这样的方案也可以通过先切 x_i 得到，所以 f_{S,i} 要减去它。

但还有一个问题，如果先按 x_i 切的可以用一种先切 y_j 的方案得到，该怎么算。首先，如果有一个点 A，x\le x_i 且 y \gt y_j，那么先切 x_i 这个点会分到左边，先切 y_j 会分到右边，又因为此时一定有点在 T_{x_i} 中，且不在 T_{y_j} 中（因为 |T_{x_i}|=i\gt j-1=|T_{y_j}\setminus \{A\}|），此时这两个点的偏序关系就会反转，序列就无法等价。所以要求 T_{y_j}\subseteq T_{x_i}（这个要求在都按 x 切时显然成立），而符合这个要求的一定合法，所以转移加上这个要求即可。

先按 y 切也是类似的。

所以把所有切法放在一起整理写一个转移：

f_i=dp_{T_i}-\sum_{j\lt i \cap T_j\subseteq T_i}f_jdp_{T_i\setminus T_j}

那 dp_S 计算就显然了：

dp_S=\sum_i f_idp_{S\setminus T_i}

转移已经做完了，但状态数看起来很爆炸，可实际上只有 O(n^4)。因为考虑每一个合法状态都是平面上一个矩形（四条分割线）框起来的点集，而不同的矩形只有 O(n^4) 种，算上转移复杂度是 O(n^6) 的。

upd:

2025.6.3：修正了一处式子错误（f 和 dp 都乘了 dp_{S\setminus T_i}）