AGC010E Rearranging

题意：给出一个长度为 的序列 。

玩家 A 会将序列 任意打乱，然后玩家 B 进行操作，每次可以将两个相邻且互质的数交换。

玩家 A 希望最终序列的字典序尽量小，而玩家 B 希望最终序列的字典序尽量大，问最终序列。

，时限 。

---

咋这一场 DEF 都是博弈……

先考虑在给定序列后玩家 B 会如何操作。

对于那些不互质的数，操作后相对顺序不会改变。不难发现，这也是方案合法的充要条件。

于是，对于每一组不互质的对子 ，连边 ，表示 一定要在 前面。

现在求该 的最大拓扑序（列）。

根据“字典拓扑原理”，用堆贪心地进行拓扑排序，每次取点权最大的点扩展即可。

---

然后，考虑 A 的对策。

对于每一组不互质的对子 ，连无向边。先手要将无向边定向，使得形成的 的最大拓扑序最小。

对于每个联通块，我们令权值最小的点 （若有多个，则任选一个）为唯一零度点，开始向外定向。

这样能保证第一个点一定是权值最小的点。反之，若有多个零度点，则第一个点可以不是权值最小的点，更劣。

在定向时，从 开始 ，优先前往权值较小的儿子。

将 树上的边按照从上到下的顺序定向， 的返祖边也从上到下（这些边是无用的，丢掉也行）。

若不优先前往权值较小的儿子，可能该分支与其他分支联通，造成这个儿子访问顺序必晚于某个更大的数，更劣。

若不连通，则先走谁没关系。“优先前往权值较小的儿子”这一策略能保证每个联通分量先被遍历到可能的最小点，故是最优的，

确定了图之后，跑 B 的贪心即可。

复杂度 。