目录
Codeforces Global Round 13
F. Magnets
题意
给定 $n$ 个磁体，编号 $1\sim n$。磁体有三种类型 $S,N,-$，其中 $-$ 代表无磁性。允许 $n+\lfloor \log n\rfloor$ 次询问。
每次询问选择若干磁体，分成两组，然后用装置测量两组磁体之间的受力。
其中，设第 $i$ 组有 $s_i$ 个 $S$ 型磁体，$n_i$ 个 $N$ 型磁体，则受力为 $s_1s_2+n_1n_2-s_1n_2-s_2n_1$，若受力超过 $n$ 则测量装置损坏。
要求在不损坏装置的前提下在允许询问次数内找到所有无磁性磁体。
数据保证至少有两个有磁性的磁体和一个无磁性的磁体。
题解
每次询问 $1\sim i-1$ 和 $i$ 号磁体两组之间的受力，当受力不为 $0$ 时 $i$ 号磁体一定有磁性，$1\sim i-1$ 中一定恰有一个有磁性磁体。
考虑二分找到 $1\sim i-1$ 中的有磁性磁体，然后用第 $i$ 号磁体检验 $i+1\sim n$ 磁体的磁性。查询次数 $n-1+\lceil \log n\rceil$。
G. Switch and Flip
题意
给定 $n(n\ge 3)$ 枚硬币，初始时 $i$ 号硬币位于位置 $a_i$ 且正面朝上。每次操作可以交换两枚硬币位置同时将两枚硬币翻面。
要求给出方案在至多 $n+1$ 次操作内将所有硬币归位( $i$ 号硬币位于位置 $i$ 且正面朝上)。
题解
首先发现当循环 $S$ 中有两枚硬币反面朝上时，对一个反面朝上硬币，直接与他标号位置做交换直到遇到另一枚反面朝上硬币。
于是可以经过 $|S|-2$ 次操作将除这两个位置以外的其他位置归位，然后交换这两个位置即可。
对两个循环 $S_1,S_2$，直接交换这两个循环中的任意一枚硬币，即可得到上述循环，于是可以 $|S_1|+|S_2|$ 次完成归位。
如果最后剩下一个循环，当这个循环大小低于 $n$ 时，直接将一个已经归位的位置当作长度为 $1$ 的循环进行归位即可。
如果这个循环大小为 $n$，则该循环至少有 $3$ 个元素，不妨设循环中连续的三个位置为 $p_1,p_2,p_3$。
依次交换位置 $(p_1,p_2),(p_2,p_3)$，于是可以得到位置 $p_1,p_2$ 反面朝上的循环。
于是可以至多 $n+1$ 次操作完成所有归位。
H. Yuezheng Ling and Dynamic Tree
题意
给定 $a_2\sim a_n$ 表示结点 $i$ 的父结点，其中 $a_i\lt i$，接下来两种操作：
- $a_i\to \max(a_i-x,1),i\in [l,r]$
- 查询 $u,v$ 的 $\text{LCA}$
题解
考虑分块，块大小为 $O(\sqrt n)$。对结点 $i$，用 $p_i$ 维护 $i$ 在同一个块中的最远祖先结点。
于是，对于查询操作，可以类似树剖查询做到 $O(\sqrt n)$。
对于修改操作，易知 $a_i$ 最多减小 $O(\sqrt n)$ 次后 $p_i$ 固定，因为此时必有 $a_i$ 和 $i$ 不在同一个块，于是 $p_i=i$。
当一个块满足所有 $p_i=i$ 时对整块修改操作只需要用懒标记维护 $a_i$ 即可。
每个块最多进行 $O(\sqrt n)$ 次整块修改操作，每次整块修改操作复杂度 $O(\sqrt n)$，共 $O(\sqrt n)$ 个块，于是整块修改操作的复杂度为 $O(n\sqrt n)$。
对于一个询问，最多有两个部分块修改操作，暴力维护即可，时间复杂度 $O(q\sqrt n)$。
总时间复杂度 $O\left((n+q)\sqrt n\right)$。
