自动搬运

查看原文

来自洛谷，原作者为

	zjy2008 else if

搬运于2025-08-24 23:03:51，当前版本为作者最后更新于2024-09-08 19:59:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

人类智慧题喵。

先考虑 $50$ 分怎么做，按 $1\cdots N$ 的顺序依次加入点，若没有被加入就把颜色记为 $N$ 。先假设这个点 $u$ 新构成了一个颜色连通块，可以通过已知信息推导出查询应该有的连通块数。若符合期望，直接退出，开始加入下一个点。否则在 $1\cdots u-1$ 中二分第一个和它形成同一连通块的点，将这 $2$ 个联通块合并后回到第一步。

分析一下操作次数，记最终连通块数为 $C$。每次合并 $2$ 个连通块需要 $\log N$ 次查询。一个点加入完成后需要 $1$ 次查询，共有 $(N-C)\log N+N$ 次查询。

如果最后只剩下了 $1$ 个连通块，这是平凡的。

考虑把整个连通块视为一个点，建成点数为 $C$ 的新图，随便搜出一棵生成树并黑白染色。先枚举颜色 $c$，把白色点都赋为 $c$，黑色点保持原状。假设所有黑色点的颜色都不为 $c$，可以推导出应该有的连通块数。若查询符合期望，直接退出，枚举下一个颜色。否则二分所有白点中第一个和 $c$ 颜色相同的。

显然你需要交换黑白，再做一次，故操作数是 $C\log N+2N$ 的。

总操作数为 $N\log N+3N$，可以获得满分。