E. Limited Edition Shop
经过一些简单转化，要解决的是如下问题：
二维平面上有 \(n\) 个点，点有点权。\(n\) 个点横坐标、纵坐标都是 \(1\sim n\) 的排列。要求选择若干点，满足它们右下角区域的并集中的点点权和最大。
考虑 \(dp\)。设 \(dp_i\) 表示考虑到从左往右第 \(i\) 个点时（必选）答案的最大值。
如图所示，如果 \(i\) 想从 \(j\) 转移，需要加上绿色部分的点权和。这可以转化成绿色+红色部分的点权和减去红色部分的点权和。其中，绿色部分的点权和可以直接算，红色部分的点权和可以在 \(j\) 处处理。当 \(i\) 增加时，红色部分去掉一列。这一列只可能有一个点 \((i,y_i)\)。所以对于所有 \(j<i\) 且 \(y_j>y_i\)，红色部分都会减去该点权。这启示我们使用线段树维护，时间复杂度 \(O(n\log n)\)。线段树下标是 \(y_i\)，原因显然。
F. Attraction Theory
观察原始 \(p\) 序列显然是没有用的，我们改为观察 \(p\) 的桶数组 \(f\)。经过思考，发现如下事实：
- \(f\) 中有值的位置一定连续。
- 设这段连续的位置为 \([L,R]\)，那么需要满足对于所有 \(L<i<R\)，\(f_i\) 是奇数。
这两个条件都可以归纳证明。并且可以发现，这两个条件是充要的，任意一个满足条件的 \(f\) 都可以简单构造出一种合法的方案。
现在这个题就是一个纯粹的计数题了。假设 \(L=1\)，我们枚举区间长度 \(Len\)。因为 \(f\) 要满足奇偶性限制，我们不妨将 \(f\) 数组处理一下得到 \(g\) 数组。具体地，
- \(f_1 = 2g_1 + x(1 \leq x \leq 2)\)
- \(f_{Len} = 2g_{Len} + y(1\leq y \leq 2)\)
- \(f_i = 2g_i + 1(1<i<Len)\)
因为 \(f_i\geq 1\)，所以显然，\(g_i \geq 0\)。
设 \(S=n-x-y-(Len-2)\)，则显然 \(\sum g_i = \frac{S}{2}\)，因为 \(\sum f_i = n\)。所以我们要求所有的 \(\sum 2g_ia_i\)。还有一些 \(x,y,1\) 之类的常数可以稍后处理。然后发现，\(g_i\) 是相当线性的，并且只考虑 \(g\) 的和的话，各个 \(g_i\) 之间并没有什么区分，也就是说它们是对称的。因此，我们可以发现，所有方案中每个 \(g_i\) 的和是分别相同的！
也就是说，\(g_i\) 的期望值是 \(\frac{S}{2Len}\)。所以 \(\sum 2g_ia_i\) 就等于 \(cnt\sum 2\frac{S}{2Len}a_i\)，其中 \(cnt\) 是 \(g\) 的方案数。然后就非常简单的做完了。\(L \neq 1\) 的情况是类似的，可能要再推一下式子吧。常数处理是简单的，时间复杂度好像可以做到 \(O(n)\)。
为什么 \(1\leq x,y\leq 2\) 呢？如果 \(0\leq x,y\leq 1\)，那么 \(x=0\) 时 \(g_1\) 就不能等于 \(0\) 了！这样是很烦的。不过若 \(1\leq x,y\leq 2\)，那么就只需要满足 \(g_1\geq 0\) 了。非常好。