【解题报告】IOI2021-2022 集训队互测 - Day 1

这是一道集训队胡策题

$\text{Author:}$ 宣毅鸣.

考场上写了一个奇怪的搜索，后来才知道可以证明是 $\mathcal{O}(n^3)$ 的。

我的想法：

首先一个 $\text{key observation}$ 是：行列都是可以进行任意交换的，这可以给矩阵一个更好的形式，从而更容易分析。

在做暴搜的时候，可以意识到若 $a,b$ 中有一维已经完全填完了，则另外一维是可以组合计算的。大概就是看有多少个位置是 $0,1$ 均可的。

现在来考虑两行 $i,j$，如果 $a_i$ 选 $1$，$a_j$ 选 $0$，两者不冲突当且仅当第 $i$ 行看作二进制数之后是第 $j$ 行的超集。于是可以得到一个结论：

设第 $i$ 行 $1$ 的个数为 $s_i$，则若 $a_i$ 选 $1$，则对于任意一行 $j$ 满足 $s_i<s_j$，$a_j$ 必选 $1$。

这是因为如果 $a_i$ 选 $1$，那么这一行为 $0$ 的列的 $b$ 都应取 $0$；在 $s_j>s_i$ 的时候，必定存在一列 $p$ 使得 $c_{i,p}=0$ 且 $c_{j,p}=1$，如果 $a_j=0$ 就一定不满足条件了。

于是可以按 $s_i$ 对行进行排序，若先不考虑相同的 $s$ 的话，$a$ 选择 $1$ 的行一定是一段前缀。考虑一下 $s_i$ 相同的 $\text{border case}$：

• 若 $s_i=s_j$ 且这两行不完全一样，其中一个为 $1$，则另一个必定为 $1$。可以用类似上面的方法说明。
• 若 $s_i=s_j$ 且这两行完全相同，且存在一行 $k$ 使得 $s_i=s_j=s_k$，但第 $k$ 行与 $i,j$ 两行不完全一样，则 $i,j$ 中若存在一行选 $1$，那么 $k$ 一定选 $1$，于是又会导致 $i,j$ 都选 $1$。
• 若 $s_i=s_j$ 且 $s_i$ 相等的行全部完全一样，则可以不区分他们，最后算方案的时候加一个组合数。

于是可以直接暴力枚举一个前缀，算一下系数之后，计算有多少个 $b$ 是合法的。实际上上面的分类并不需要显式地写出来，因为如果 $s$ 相等的行不完全相同，且没有一次性选完这些行，则 $b$ 的方案数一定是 $0$，无需考虑。时间复杂度 $\mathcal{O}(n^2)$。

std 做法：

设 $a,b$ 中 $1$ 的个数分别为 $c_a,c_b$，满足 $c_{i,j}=a_i$ 的位置个数、$c_{i,j}=b_j$ 的位置个数分别为 $s_a,s_b$，则一组方案合法当且仅当：

$$ c_a+c_b-s_a\times s_b-(n-s_a)\times (n-s_b)=n^2 $$

同时可以证明对于任意方案，有 $c_a+c_b-s_a\times s_b-(n-s_a)\times (n-s_b)=n^2$。考虑一组 $i,j,a_i,b_j$ 对上述值的贡献，可以得到只有 $a_i=b_j=c_{i,j}$ 的时候对上面式子有 $1$ 的正贡献，又这样的对只有 $n^2$，所以上式 $\le n^2$。

同时由于每一个 $c_{i,j}$ 都至少要匹配 $a_i$ 或 $b_j$，所以上值不能 $<n^2$。

于是，每次应该贪心地选择，使得 $a_i=b_j=c_{i,j}$ 尽量多。最后如果有若干行/列 $1$ 个数相同，则有一个组合数。这里还没太看懂

复杂度也是 $\mathcal{O}(n^2)$。

树上的孤独

$\text{Author:}$ 林帮才.

考场上觉得这是本场最可做的题目，可惜自己几乎可以说是不会 $\text{dsu on tree}$。考后和机房同学们一起编出来了。

考虑一个简化情况：如果没有第一棵树，只有第二棵树，则只需要问这棵树某个子树内与子树根距离 $\le d$ 的颜色数。

如果这是在序列上，我们可以考虑主席树，对每一种颜色维护最后一次出现位置，在右端点对应主席树上进行查询。套到树上，可以对每一种颜色维护子树内最浅的出现深度，设为 $\text{mind}_c$，则子树内距离子树根 $\le d$ 的颜色数就是 $\text{mind}$ 的一个前缀。因此需要主席树来维护，下标 $i$ 处维护 $\text{mind}=i$ 的颜色数是多少，这样就可以查询前缀了。

考虑如何构建这棵主席树，如果只是要维护每种颜色的 $\text{mind}$，可以考虑线段树合并。但是由于要维护的是上面这个东西，所以线段树合并不够灵活。考虑 $\text{dsu on tree}$，主席树从自己的重儿子处继承即可。

注意到这里的复杂度是 $\mathcal{O}(m\log^2 m)$，但是查询是单次 $\mathcal{O}(\log m)$ 的，所以复杂度没有问题。

再考虑加入第一棵树，由于点数只有 $20$，所以可以直接暴力检查第一棵树中每一个颜色是否在第二棵树的连通块内出现。简单的方法是再开一个线段树合并，但是这样会带 $\log$，复杂度变成 $\mathcal{O}(nq\log m)$，无法通过。

观察到这个强制在线的方式很有深意，他只对距离进行强制在线，但是并未对询问点强制在线，因此实际上还是可以离线下来，在 $\text{dsu on tree}$ 的时候顺便维护第一棵树子树中每种颜色，在查询的第二棵树子树内的最浅深度，最后再检查是否真的在询问的连通块中即可。

于是就去掉了线段树合并的 $\log$，总复杂度是 $\mathcal{O}(m\log^2 m+q\log m+nq)$。