A - ><
左右分别是 >，< 的一定可以设为 \(0\)，倒推即可，最后对两类限制取 max。
B - Two Contests
感觉这题比 C 难...
给定 \(n\) 条线段，把它们分成两个集合（均非空），最大化每个集合中线段交的长度的和。 \(n\leqslant 10^5\)。
考虑左端点最靠右的区间 \(p\) 和右端点最靠左的区间 \(q\)，如果它们被分到了同一个集合，那么另外一个集合肯定放其它线段中长度最大的那条，答案为 \(\max(r_q-l_p+1,0)+mxlen\)。
如果不在一个集合，考虑添加每个线段到集合中会造成的收益，现在等价于每条线段有两个属性 \(a_i=\max(r_i-l_p+1,0)\)，\(b_i=\max(r_q-l_i+1,0))\)，现在要最大化 \(\min\limits_{i\in S_1}\{a_i\}+\min\limits_{i\in S_2}\{b_i\}\)，只需按 \(a\) 从小到大排序，枚举 \(a\) 的最小值同时计算前缀 \(b\) 的最小值即可。复杂度 \(O(n\log n)\)。
C - Neither AB or BA
考虑一个长为 \(n\) 的只含有 A，B，C 的串，每一次可以消掉相邻的两个字符，且这两个字符不能是 AB 或 BA，求长为 \(n\) 的可以通过若干次操作清空的串的个数。\(n\leqslant 10^7\)。
考虑把偶数位置上的所有 A 和 B 翻转，现在相当于一次不能抹去 AA 或 BB，那么现在序列不能被消除的条件当且仅当 A 和 B 的个数都不超过 \(\lfloor\dfrac{n}{2}\rfloor\)。考虑容斥计算，用所有的减去不合法的，钦定 A 的个数超过 \(\lfloor\dfrac{n}{2}\rfloor\)，剩下随便选 B 或 C，然后乘上 \(2\) 就是总共的不合法序列个数。复杂度 \(O(n)\)。
D - Balance Beam
感觉这题比 E 难...
有 \(n\) 个长度都为 \(1\) 的平衡木，第一个人（A）需要花费 \(a_i\) 秒通过第 \(i\) 块平衡木，第二个人（B）需要花费 \(b_i\) 秒通过。现在你可以随意排列平衡木，A 会从最左面向右走，B 会随机一个位置开始向右走（不一定从边界开始），两人同时开始，问 A 能够在 B 到达终点前碰到（碰到后可以重新被超越）他的概率最大是多少，输出最简分数。\(n\leqslant 10^5\)。
设 \(s_a=\sum a_i\)，\(s_b=\sum b_i\)，我们建立两个人的时间-位移图象，先假设 \(b\) 也从起点走，那么两条线都从 \((0,0)\) 出发，到 \((n,s_a)\) 和 \((n,s_b)\)。现在考虑 \(b\) 从某个位置开始走，这就相当于把 B 的图象沿着 \(y\) 轴向下平移，其和 \(x\) 轴的交点 \(k\) 就代表从 \(k\) 开始走。那么从 \(k\) 开始走 A 还能追上 B 当且仅当这两个图象还有交点，临界态一定是两个图象的交点是一个点或一条线段。
我们现在设平移到交点为 \((k,0)\) 时为临界态，首先我们枚举 \(k\) 在哪一块平衡木上（设为 \(i\)），现在我们考虑排列剩下的平衡木使得 \(k\) 最大。
我们考虑以下一条线：先沿着 B 的图象走，当两图象第一次相交以后沿着 A 走，那么我们最后一定会走到 \((n,s_a)\)。我们现在希望让 \(k\) 尽量大，也就是让放在 \(i\) 平衡木后面的平衡木数量尽量少，也就是这条线上升的尽量快。
我们有一个 naive 的观察：这个新图象在平衡木 \(j\) 中上升不会超过 \(\max(a_j,b_j)\)，那么是否有 \(b_i+\sum\max(a_j,b_j)\geqslant s_a\) 时就可以达到呢？确实如此，考虑我们把 \(b_j>a_j\) 的平衡木都放到 A 和 B 图象的交点前，\(a_j>b_j\) 的放到交点后，那么总是能达到最大值。所以我们把所有平衡木按 \(\max(a_j,b_j)\) 从大到小排序，对于固定的 \(i\)，二分找到最短的前缀使得 \(\max(a_j,b_j)\) 的前缀和不小于 \(sa-b_i\)，这样就找到了整数部分；对于小数部分，设 \(t\) 为 \(\max(a_j,b_j)\) 之和，\(s\) 为整数部分，临界态一定同时经过了点 \((n-s,sa-t)\) 与 \((n-s-1,sa-t-b_i)\)，这样可以推出 \(k\)，最后对每个 \(i\) 取最优答案即可。复杂度 \(O(n\log n)\)。
E - Prefix Suffix Addition
你有一个长为 \(n\) 的序列 \(x_1,x_2,\dots,x_n\)，一开始全部为 \(0\)，你现在可以以任意顺序进行任意次以下两种操作：
- 选定整数 \(k(1\leqslant k\leqslant N)\) 与不下降非负序列 \(c_1,c_2,\dots,c_k\)，对所有 \(1\leqslant i \leqslant k\)，令 \(x_i\) 加上 \(c_i\)。
- 选定整数 \(k(1\le k\le N)\) 与不上升非负序列 \(c_1,c_2,\dots,c_k\)，对所有 \(1\leqslant i \leqslant k\)，令 \(x_{N-k+i}\) 加上 \(c_i\)。
问最少进行多少次操作使得最后对任意 \(i\) 有 \(x_i=A_i\)。\(n\leqslant 2\times 10^5\)。
考虑只有第一种操作的情况下的最小花费：令 \(A_0=A_{n+1}=0\)，则应该是 \(\sum A_i<A_{i-1}\)，只有第二种类似。
我们考虑第一种操作对位置 \(i\) 的总贡献为 \(x_i\)（变量重名了但这不重要），则第二种操作对位置 \(i\) 的总贡献为 \(A_i-x_i\)，那么这一种划分方式的总代价是 \(\sum\limits_{i=1}^{n+1} [x_i<x_{i-1}]+[A_i-x_i>A_{i-1}-x_{i-1}]\)。设 \(f(i,j)\) 表示考虑了前 \(i\) 个数，\(x_i=j\) 的最小代价之和，不难发现有以下三条性质：
固定 \(i\)，\(f(i,j)\) 随 \(j\) 上升单调不增。
对于 \(f(i,j)\) 相同的 \(j\)，只需要保留 \(j\) 最大的那个。
\(f(i,0)-f(i,A_i)\leqslant 2\)。
我们只需要把 \(f\) 相同的合并到一起转移，转移是一个 max 卷积的形式，表示使得 \(f(i,j)=f(i-1,0)+0/1/2\) 的最大的 \(j\) 是多少，具体实现可以见代码，复杂度是线性的。
F - Two Pieces
咕咕咕。