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 ight floor + left lfloor dfrac n4 ight floor + left lfloor dfrac n8 ight floor + cdots + underbrace{1 + 1 + cdots + 1}_{ ext{less than } m} = O left( n + m ight))，所以复杂度为 (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)) 为状态二，则将子树取反。
（这题代码在有了）