【解题报告】Codeforces Global Round 19
赛时 $\tt{ABCDEF}$，$\text{rank 151}$。
改题 $\tt{GH}$。
G. Birthday
第一步个人感觉比较难以猜到（除非写爆搜），剩下的部分有一个地方想复杂了。
通过各种方式，可以证明最后的答案是 $2^{\lceil\log_2 n\rceil}$，证明如下：
考虑若最后的答案含有奇质因子 $p$，注意到一步操作 $(x,y)\to (x+y,|x-y|)$ 不可能将两个不同时为 $p$ 的倍数的数，都变成 $p$ 的倍数。
目标是 $x=2^{\lceil\log_2 n\rceil}$，我们首先希望把每个数字都变成 $2$ 的整次幂，然后如果有 $0$ 的话，就能 $(x,0)\to (x,x)\to (2x,0)$ 来 $\times 2$ 了。
考虑 $\dfrac{x}{2}$ 这个位置，左右可以拼起来组成若干个 $x$，产生的另外一个数字可以看作是一个子问题，每个元素都变成两倍。前面可能剩下一些，但那也是个子问题。
当 $n\le 2$ 的时候，本身就都是 $2$ 的整次幂了，可以直接返回。注意到这个序列中，元素个数有 $n$ 个，种类只有 $\mathcal{O}(\log n)$，因此肯定存在两个相等的数字（$n=3$ 是最紧的，但是证明确实有），只需要 $(x,x)\to (2x,0)$，然后拿这个 $0$ 做上面的事情就行。
最后肯定还要一个 $(0,x)\to (x,x)$。
H. Minimize Inversions Number
感觉是只需要 $\text{Hint 1}$ 就能过了的题。
首先考虑将某一个单点 $i$ 换到最前面，对逆序对的贡献，应该形如：
$$ c_i=\sum_{j=1}^{i-1} [p_j<p_i] - \sum_{j=1}^{i-1}[p_j>p_i] $$
在有多个的时候呢？应该形如：
$$ \sum_{i\in S} c_i + f(S) - (\binom{|S|}{2} - f(S)) $$
其中 $f(S)$ 是 $S$ 的逆序对数。相当于把 $S$ 中原本就有的逆序对要加回来，但是在 $c$ 中我们认为 $S$ 里的顺序对会变成逆序对，也需要减去。如果设一开始的逆序对数为 $x$，那么某一组方案的答案就是：
$$ x+\binom{|S|}{2} + 2f(S) + \sum_{i\in S} c_i $$
前面的 $x+\binom{|S|}{2}$ 在 $|S|=k$ 固定时是定值，只要最小化后面的部分。尝试构造 $d_i$，满足后两项的值恰好是 $\sum_{i\in S} d_i$（就像把 $2f(S)$ 吃进去）。那么应该有：
$$ d_i=\sum_{j=1}^{i-1}[p_j<p_i]-[p_j>p_i]+2\sum_{j=i+1}^n [p_i>p_j\land j\in S] $$
考虑 $[p_i>p_j\land j\in S]$ 什么时候满足。一个关键性质是：
若 $i\in S$，$\forall j$ 满足 $j>i,p_j<p_i$，有 $j\in S$。
证明暂鸽。然后就可以改成：
$$ d_i=\sum_{j=1}^{i-1}[p_j<p_i]-[p_j>p_i]+2\sum_{j=i+1}^n [p_i>p_j] $$
时间复杂度 $\mathcal{O}(n\log n)$。