Codeforces Round 1049 (Div. 2) 一些 idea
A
B
设 y 有 k 位
\(x + y | x * 10 ^ k + y \Leftrightarrow x + y | x (10^k - 1)\)
很明显，y 可以取 ：\(2x\), \(8x\), \(10^k - 1 - x\) (这里 \(k\) 可以取 \(9\))
C-E
C-E 的关键是，拆贡献。
如果一个信息是由多个信息决定，但是可以通过简单的运算得到，那么就可以拆开来。
比如背包是求和，所以可以一个一个加；而函数复合不能拆，只能由两个信息合并。
拆贡献的关键是独立性。交换律说明每一部分都是独立的。
C
\(cost\) 是 \(r - l\), 也就是说一次的改变量是 \(delta_{a_l} + delta_{a_r} + r - l\)
而 \(delta_{a_l}\) 和 \(l\) 由节点 \(l\) 决定，\(delta_{a_r}\) 和 \(r\) 由节点 \(r\) 决定。
加法显然有交换律，所以可以拆贡献（其实这里没有交换律也可以，因为顺序是固定的：先找到 \(l\) 再找到 \(r\)）
然而 \(delta\) 由两者决定，更具体来说是两者的下标奇偶决定，因此需要分开来考虑。
D
如果是奇数，先删去一个区间。
同样是 \(r - l\), 拆贡献，选为 l 则为 -l，选为 r 则为 +r。
每个东西两种选择会有一些差值。这决定了选 l 和选 r 的 “好的程度”。
如何比较好的程度？
考虑原先全选 l，然后把 l 变 r 的好处是 r - (-l)。我们选择最大的这 n / 2 个。
E
博弈题，最终答案是一些东西取 min/max。我们确定一个数组的答案是困难的，但是确定 >= x 是简单的。
这是一种常见的拆贡献，原因是 \(min = x\) 是困难的，不可拆的，\(min >= x\) 是可以拆的。
f(a) = ge(fa(a), 1) + ge(fa(a), 2) + ...
ge(fa(a), x)，我们可以离散化，将 ge(x) 和 less(x) 分开，这样就转化成了 E1。