考试全程处于自我窒息的半思考半强迫症状态，思维跳跃不连贯，不能静下来思考等等。
一股脑死刚T1，好歹把式子磨出来，最后写错了个地方没查出来无奈弃疗。。。只得花了几分钟打了T2暴力防爆零。。。
T1想到正解，加减写错，天赐7分orz
T2想到是splay维护dp差分数组，有做过该类的题，但是理解很不深刻，之前没有弄明白，觉得自己写不出来。
A. Inverse
题意：给出[1,n]的排列P，K次等概率选取区间翻转，求期望逆序对数。n<=500 K<=50
这个范围允许我们存点对的相对大小，于是设(f_{k,i,j})为前k轮，(i<j,P_i>P_j)的概率。
那么(Ans=sumlimits_{i=1}^n sumlimits_{j=i+1}^n f(K,i,j))
考虑转移：暴力的做法是枚举([l,r])，较暴力的是枚举对称点算系数。
把转移用式子形式化写出。为了方便(g_{i,j})是第k-1维的数组
按照l,r,i,j的大小关系分类讨论
1.l,r不包含i j，直接算系数转移
2.(l<=i<=r<j)
(f(i,j)=sumlimits_{l=1}^i sumlimits_{r=i}^{j-1} g(l+r-i,j))
发现第二维和l r无关，所以可以做前缀和
(f(i,j)=sumlimits_{l=1}^i (S_1'(l+j-i-1,j)-S_1'(l-1,j)))
(=S_1(j-1,j)-S_1(j-i-1,j)-S_1(i-1,j))
3.(i<l<=j<=r)，与2同理
4.(l<=i<j<=r)
i,j的大小关系变化，但如果要直接得到对应dp值，还需要加几组转移。
实际上可以(=sumlimits_{l=1}^i sumlimits_{r=j}^n(1-g(l+r-j,l+r-i)))，然后就可以化简了
发现两边都有变量，但是做差后可以得到常量
于是设(h(i,j)=f(i,i+j))
(=i imes(n-j+1)-sumlimits_{l=1}^i sumlimits_{r=j}^n h(l+r-j,j-i))
后面式子(sumlimits_{l=1}^i (S_3'(l+n-j,j-i)-S_3'(l-1,j-i))=S_3(n+i-j,j-i)-S_3(n-j,j-i)-S_3(i-1,j-i))
复杂度(O(Kn^2))
B. Subsequence
题意：序列A的子序列B，定义权值为(sumlimits_{i=1}^k B_i imes i)，求(kin[1,n])的最大权值。n<=1e5,|A_i|<=1e7
(O(n^2))DP好说，(f(i,j))为前i个选了j个的最大权值。
(f(i,j)=max(f(i-1,j),f(i-1,j-1)+A_i imes j))
要求完整第二维，而枚举两维的复杂度不可接受，所以可以猜测一些比较强的性质。
之前做过类似的题，排序后形式只多了个常量，参考那题的做法，可以猜正解是平衡树维护差分表
而这样的性质支持是：两种转移存在分界点。考场上一般硬核打表
这题的dp具有该性质，然后码棵splay，在splay上二分找到分界点，支持区间加，最后前缀和输出。
下午想了好久，因为之前就不是很懂
正确性：存在分界点，那么直接考虑最终答案数组的第二维，一个物品在k个的最优集合中出现，那么在k+1 k+2 ... n的后缀全部存在
所以用平衡树维护序列，同时权值差分，因为要加等差数列，这样可以转化为区间加。
splay上二分的时候记录左边的sz，用两种转移的不等式判断分界点位置，加点后splay在右儿子上加法标记
为啥是等差数列手模下2 2 3就知道了
复杂度(O(nlogn))
C. Convex
思路大概明白，细节还不太会。
先咕了