CF1762D GCD Queries
增量维护。
CF2196F Indivisible
CF2124G Maximise Sum
CF1364E X-OR
找到 0 就可以通过 \(n-1\) 次找出排列。
0 可以增量维护，唯一的问题是 \(p_x\) 不是 0 要问一次 \(p_y|p_i\)。
由于不是自适应，可以 shuffle 后问就没问题了。
最后检查哪个是 0 就随机几个数问一下。
CF2096G Wonderful Guessing Game
三进制分组，如果这个前一半后一半是我们自己定的那么可以问 \(S_0+S_1\)，在 \(S_2\) 中就是返回 N。
再问一次按照 \(\mathrm{pop}(x)\bmod 3\) 分组的，这样可以得到缺失位的信息。
现在处理 \(|S_0|,|S_1|,|S_2|\) 差距过大的问题，考虑分治重编码，这样每一位变成每一层中作为第几个儿子。
至少有两个集合大小相同，那么问他们两个就好了。（证明可以分讨一下？）
CF1887E Good Colorings
可以行列转二分图，每次可以给两个点之间加上一条边，最后要找到一个四元环满足边都是不同色的。
初始边数和点数相等，所以一定有一个环，且颜色都不相同。
那么每次在环上二分加边，把颜色相同的那一侧丢掉。
CF2006F Dora's Paint
考虑行列转二分图，若 \((x,y)\) 是 1 就连边 \(y'\to x\)，是 2 就连边 \(x\to y'\)。
那么美丽度就是拓扑序数量。
由于是完全二分图，所以他一定是分为若干层，每层内都是同色的点，他们会向后面所有不同色的层的点连边。美丽度可以定义为每一层的点数的阶乘之积（注意第一层没有贡献，因为他们另一维是空的）。
修改就是改变一条边的方向。如果原本图上有环，我们必须改变所有环的公共边。二分完全图中如果存在环，那么中间存在某个边，无论他的定向如何都可以得到一个更小的环。根据这样归纳一定存在一个四元环。所以只需要考虑这四条边翻转方向的答案，直接跑 4 次就好。
现在考虑原图是个 DAG，那么如果改变的边跨过多层，那么一定有环。那么只能是相邻层之间的边。且你会把这条边的两个端点变成两个新的层。
假设有相邻两层，点个数分分别是 \(x,y\)，那么去掉的贡献是 \(\frac{1}{xy}\)，而选择两个的点的方案是 \(xy\)，所以其实贡献就是 1。
第一层较为特殊，贡献是 \(x\)。
然后是实现细节：如何找出一个拓扑序，或者找出一个四元环。
根据完全二分图的性质，同侧的点一定是按照 \(\deg_{in}\) 排序的。
那么可以双指针归并两部点，维护 2 类边全局 \(\deg_{in}\) 减标记（被减错的一定已经加入拓扑序中了）。
找出四元环：考虑拓扑序做了一半，然后没有 \(\deg_{in}=0\) 的点了。
那么一定要有 \(\deg_{in}=1\) 的点，否则翻转一条边仍然无法满足条件。
考虑 \(\deg^{in}_{u}=1\)，从他往前跑 4 条边，一定可以找到一个四元环。
使用桶排序，时间复杂度线性。