A. Inverse

似乎这类问题的套路都是考虑每一个点对。

然后考虑一个 dp 。

设 $f_{k,i,j}$ 表示考虑后 $k$ 轮，最终 $i$ 在 $j$ 左面的方案数。

对于每个 dp 值可以简单枚举翻转区间， $O(n^2)$ 转移。

然后发现这个玩意可以优化，如果枚举翻转区间的左端点，那么问题是前缀和。

然后发现现在的问题仍然是前缀和。

所以对 dp 数组作两次前缀和就完事了。

考场上看到这个 $n^2$ 的转移就人傻了，没有仔细去想这个式子。

当发现可以搞个前缀和优化的时候时间已经不多了，所以有些遗憾。

B. Subsequence

观察样例可知一个结论，在 $i-1$ 的选择中出现的，在 $i$ 的选择中也会出现。

所以可以考虑每步贪心选择当前最优。

当选择了一个权值，贡献是前缀加当前点权值，后缀加自己点权值。

可以把后缀加的部分视作斜率，于是得到一个简单的根号算法维护重构凸包的算法。

因为评测机开了 noilinux，所以这个算法没戏。

我还是太天真了，没有想象到 noilinux 的威力，所以挂成了暴力分。

正解是一个平衡树维护差分 dp 数组的东西，两个月前打过。

大概思想就是在平衡树上二分找到合适的位置，然后后缀加当前权值操作。

C. Convex

计算几何知识还是太差了。

求多边形面积不一定非要选多边形上的点，选择原点然后跑叉积可能会大大减轻计算的难度。

对于绝对值跑个类似旋转卡壳的东西就可以直接维护和。

然后发现问题分两个部分，一部分形如 $\sum \limits_{i=l}^r (r-i)*v_i$。

发现这个玩意作两遍前缀和，然后和前缀和搭配着用就可以解决了。

另一部分形如 $\sum \limits_{i=l}^r A \times B_i$，其中 $A,B_i$ 为向量。

解决这个问题的办法是对 $B_i$ 直接做个前缀和，化开叉积的式子就可以验证是正确的。