CF2006
A
发现 \(01\) 和 \(10\) 相差不超过 \(1\)，就是关注 \(01\) 段个数，中间插入 \(01\) 不影响段的奇偶性，转化为路径首尾不同
一种较优策略是先手固定根，其实还可以让后手固定根，当 \(c_0=c_1\) 答案可能会大 \(1\)，分讨即可
B
显然一条边只属于两条路径，暴力维护即可
C
考虑证明当 \(\gcd c=2^i\) 时有解
不妨考虑结束条件，排序，相邻两项必然奇偶性不同，间隔一项的平均数等于中间项，那么推出所有数的间隔相等，且不为 \(2\) 的倍数。事实上你发现运算都是将任意两个数的差 \(a\) 和 \(b\) 进行 \(a+b,a-b\) 和 \(\dfrac{a}{2}\) 的操作，那么得到的必然是所有差的 \(\gcd\)
貌似还是有点感性（
D
好题
枚举全排列肯定不行，寻找最优策略。发现是 \(\text{rank}\) \(n,1,n-1,2\dots\) 排列，证明考虑交换必然不优，那么相当于 \(n\) 和 \(1\) 配对，以此类推
\(ab\le k\)，通常考虑根号分治或者 \(n\ln n\) 的东西。考虑 \(B=\sqrt{n}\)，那么将序列分成 \(\le B\) 和 \(\ge B\)，发现 \(c_{\le B}\ge c_{>B}-1\)，不妨将 \(\le B\) 和 \(>B\) 的数分别列出，\(>B\) 从大到小，\(\le B\) 从小到大，将可以配对的连边，那么这是个二分图，且对于 \(>B\) 的连边是个前缀，转化为了二分图匹配问题。
考虑 hall 定理，要求 \(>B\) 完美匹配，当选了 \(i\)，那么必然选 \(>i\)，会加强限制条件。发现有用的段只有 \(B\) 个，对每个 \(>i,>\dfrac{n}{i}\) 考虑即可，注意要考虑全局，也就是 \(>0,>B\) 的。考虑如何调整，显然是 \(\max\rightarrow 1\)，其实是 \(\dfrac{\Delta c}{2}\)，有时候还要加 \(1\)，注意细节，且通过构造可知这玩意可以直接取 \(\max\)
实现的时候可以对 \(i<B\) 处理每个询问
E
预处理每个点的最远距离。考虑维护直径，每次至多动一个端点，转化为区间加，查 \(\max\)，然后就做完了
标签：le,dfrac,01,CF2006,max,考虑 From： https://www.cnblogs.com/Tagaki-san/p/18391171