Solution. Codeforces Round #781
现在是 12:35，只做了 ABC，简单记一下关于 DE 的想法。
D，给了 30 次询问，从信息论的角度看，$\left\lceil\log_2 10^9\right\rceil$ 恰好等于 30，那是否要求了每一次询问都将可能的答案减半，或者每次询问确定一个二进制位这样。
能够想到的就是可以通过 $\gcd(x,x+prime)$ 来判断 $x$ 是否拥有 $prime$ 这个质因子。
E，不知道或运算怎样会比较好维护，$10^5$ 3s 的话莫队然后 $O(\log n)$ 的拓展区间，总复杂度 $O(n\sqrt n\log n)$ 也问题不大，总之还是在于不会描述按位或。
这次 Editorial 居然这么快 /jy
看到 E 的 Other Solutions 里给了一种莫队 + van Emde Boas tree 的做法 /fad。
C fst 了，写的二分弄巧成拙，明天写一下 CDE。
specialist -> pupil
这个 cf 打的只能说是心态爆炸
C. Tree Infection
可以轻易的被转化为序列问题，因为每个点的儿子都是相互独立的。
整个传染的过程可以被分为两部分，一是对于每个非叶子结点的儿子而言（另外特殊考虑根结点），我们都需要至少对其中一个儿子进行「注射」，否则它们也不可能通过「传播」被感染；二是在所有非叶子结点的儿子中都存在被感染的结点后，现在「注射」操作被闲置下来，可以帮助加速「传播」的过程。
对于前者，我们知道「注射」过程一定是从儿子数量多的开始，这部分由于排序是 $O(n\log n)$ 的，当然如果精细实现似乎也可以省去排序做到线性；后者我们实际上每次也会选择未被感染儿子数量多的进行「注射」，我当时这里选择了二分一个时间，但是你就暴力的模拟这个过程也是可行的，因为考虑到总点数为 $n$，每次我们花费 $O(1)$ 的代价去扫一个结点的时候，也就必然对应着未被感染结点数量 $O(1)$ 的减少，故总复杂度为 $O(n)$，二分反倒是 $O(n\log n)$ 的。
我的二分：
for(int x: opt) tmp += x - mid; // fst, wrong answer on testcase 20
for(int x: opt) tmp += max(0, x - mid); // accepted这玩意居然能过 pretests 而且在 20 才 wa /dk
D. GCD Guess
确实可以做到一次询问确定一个二进制位。
首先我们知道 $x\bmod 2^0=0$，接下来考虑如果知道 $x\bmod 2^k=r$，如何求 $x\bmod 2^{k+1}$。
$x\bmod 2^k=r$ 意味着 $x$ 可以被表示为 $t\cdot 2^k+r$，那么：
$$
x\bmod2^{k+1}=\begin{cases}
r &\mathrm{if}\ 2\mid t,\\
2^k+r &\mathrm{otherwise}.
\end{cases}
$$
我们实际上可以通过 $\gcd(t\cdot 2^k,2^{k+1})=\gcd(x-r,x-r+2^{k+1})$ 来判断 $t$ 的奇偶性，当结果为 $2^{k+1}$ 时 $t$ 为偶数。
由于询问的 $\gcd(x+a, x+b)$ 要求 $a,b>0$，所以给询问的数加上 $2^k$，$\gcd((t+1)2^k,2^{k+1})=\gcd(x+2^k-r,x+2^k-r+2^{k+1})$，对应的，结果为 $2^{k+1}$ 时 $t$ 为奇数。
E. MinimizOR
Lemma. 答案必然在最小的 31 个数中产生。
这个 31 是基于二进制串长度的，本题中 $a_i\le 2^{30}$。
在有了这一结论之后，就可以暴力的用线段树维护最小的 31 个数，暴力的枚举任意两个数或起来然后计算答案，假设 $n,q$ 同阶，总复杂度为 $O(n\log n\log a_i+n\log^2 a_i)$。
然后我们希望来证明这个结论。
我们知道 $a_i$ 共有 30 位，从高位向低位依次考虑，对于每一位，我们有这么三种情况：
- 当前位全为 1，此时无论如何选择，最终答案的当前位必然为 1。当前位不会对答案的选择造成任何影响，我们可以直接忽略当前位。
- 当前位有不少于两个 0，那么答案必然从当前位为 0 的数中产生，同时这样选也满足使得选出数尽量小的原则。
- 当前位有且仅有一个 0，最终答案的当前位必然为 1，我们不一定会去选择当前位为 0 的那个数，请注意此时我们可能会违背使得选出数尽量小的原则，但尽管如此，至多也只有一个较小的数被忽略。
那么最极端的情况就是 case 3，此时每一位都可能造成至多一个较小的数被忽略，但是最后一位是特殊的，此时已经是我们的最后一次决策，我们完全可以选择那个 0，答案必然不劣。至此，我们就证明了会被忽略的较小的数至多是 29 个， 那么在最坏情况下，答案会来自于从小到大的第 30 个数以及第 31 个数。
于是，答案必然在最小的 31 个数中产生。$\blacksquare$
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
