Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics)
A
设 \(s_i\) 为前缀左括号个数减右括号个数，每一段 \(s_i<0\) 的区间都需要操作，操作还需包含一段负区间末尾 \(s_i=0\) 的位置。
B
考虑第 \(k\) 位，将所有数在模 \(2^{k+1}\) 意义下考虑，若两个数的和 \(\in [2^k,2^{k+1}-1] \cup [2^k+2^{k+1},2^{k+2}-2]\)，则其在第 \(k\) 位为 \(1\)，通过双指针统计个数，按奇偶性计算即可。
C
设 \(S(x)\) 为右部图的点 \(x\) 在左部图的与其相连的点集，给每个点集 \(S(x)\) 初始权值为 \(c_x\)。将相同的点集进行合并，合并后的权值为相同的点集权值和。最终答案为所有剩余点集权值的 \(\gcd\)，这里不考虑空集。
D
先将序列翻转，将单调不升变为单调不降。设 \(f_{i,j}\) 为考虑了攻击力 \(\leqslant i\) 的选手，且攻击力为 \(i\) 的选手有 \(j\) 个的最大收益，得转移为：
这样转移就能保证单调不降了。这里对 \(k\) 的枚举范围进行限制，当前攻击力为 \(l_i\) 时，对于 \(l_i\) 枚举前 \(n\) 项，对于 \(l_i+1\) 枚举前 \(\frac{n}{2}\) 项，对于 \(l_i+2\) 枚举前 \(\frac{n}{4}\) 项，\(\dots\) ，这里相当于模拟了所有攻击值的二进制加法，因为对于每个 \(i\)，其有效的状态数为 \(n + \left \lfloor \dfrac n2 \right \rfloor + \left \lfloor \dfrac n4 \right \rfloor + \left \lfloor \dfrac n8 \right \rfloor + \cdots + \underbrace{1 + 1 + \cdots + 1}_{\text{less than } m} = O \left( n + m \right)\)，所以复杂度为 \(O(n(n+m))\)。
E
先考虑 \(01\) 序列，发现 \(00\) 和 \(11\) 都是稳定的，因此只需处理 \(01\) 交替的段。考虑枚举一个分界线 \(k\)，将 \(\leqslant k\) 的位置都看作 \(0\)，所有 \(>k\) 的位置都看作 \(1\)，若位置 \(i\) 在 \(01\) 表示下的最终结果为 \(0\)，则位置 \(i\) 最终的值 \(\leqslant k\)，否则 \(>k\)。得当分界线从 \(k\) 枚举到 \(k+1\) 时，位置 \(i\) 的结果从 \(0\) 变成了 \(1\)，则位置 \(i\) 最终的值为 \(k\)。
所有分界线得出的序列中 \(01\) 交替的段的最长长度除以 \(2\) 为操作次数，因为每次操作后 \(01\) 交替的段的长度会减少 \(2\)。
考虑求出每个位置向两边扩展 \(01\) 交替的段的最长长度，根据该长度分类讨论即可得出当前位置的最终的值。可以通过 \(ST\) 表预处理最值，然后二分求解最长长度。
F
不难发现答案上界为 \(n\)，其可以通过数学归纳法证明，去掉一个叶子就为一棵 \(n-1\) 个点的树，该叶子要么最小，要么最大。
先考虑判定无解的情况。先将树定为有根树，考虑树上的一条边 \((fa,x)\)，若其没有被路径覆盖，则可以不考虑这条边，若其被覆盖了，那么该边一定满足这两种状态之一：\(c_x < c_{fa},c_x > c_{fa}\)。
一条路径就是使若干边的状态相同或者相反，那么可以用并查集来判定是否有解。
发现答案具有单调性，可以二分求解，考虑用树形 \(DP\) 来判定二分。当前二分的值为 \(k\)，设 \(f_x\) 为边 \((fa,x)\) 为状态一时 \(c_x\) 的最小值，不难发现当边 \((fa,x)\) 为状态二时 \(c_x\) 的最大值为 \(k+1-c_x\)，将 \(x\) 子树内值域取反即可。
考虑 \(x\) 的子树 \(y\) 对 \(c_x\) 的限制：
若 \((x,y)\) 没被覆盖，则不考虑。
若覆盖 \((x,y)\) 和覆盖 \((fa,x)\) 的路径有交，即 \((x,y)\) 和 \((fa,x)\) 的状态有关联，那么已知 \((fa,x)\) 为状态一时，就能确定 \((x,y)\) 的状态了。\((x,y)\) 为状态一时，得 \(c_x > c_y\)，得其对 \(c_x\) 的限制区间为 \([c_y+1,k]\)，\((x,y)\) 为状态二时，得 \(c_x < c_y\)，得其对 \(c_x\) 的限制区间为 \([1,c_y-1]\)。
若覆盖 \((x,y)\) 和覆盖 \((fa,x)\) 的路径无交，则 \(y\) 子树内的状态选择和 \((fa,x)\) 的状态无关，考虑 \(y\) 子树内的状态的某种选择对 \(c_x\) 的限制区间为 \([l,r]\)，得另一种状态对 \(c_x\) 的限制区间为 \([k+1-r,k+1-l]\)，得 \(y\) 子树对 \(c_x\) 的限制区间为 \([l,r] \cup [k+1-r,k+1-l]\)。
那么将 \(x\) 的所有子树对 \(c_x\) 的限制区间取交，限制下的集合最小值即为 \(f_x\)。发现 \([l,r] \cup [k+1-r,k+1-l]\) 不一定是一段连续的区间，因此要用线段树扫描线来维护。
实际上可以更简便，发现若 \([l,r] \cup [k+1-r,k+1-l]\) 不是一个连续的区间，则其一定是两个以 \(\frac{k+1}{2}\) 为对称轴的区间，那么可以维护中间空出的部分一定包含 \(\frac{k+1}{2}\)。因此维护区间的交和中间空出的部分的并即可线性转移。
构造方案时，可以在树上差分打标记，若边 \((fa,x)\) 为状态二，则将子树取反。
（这题代码在有了）