T1
设f[i][j][k]代表k次操作后a[i]<a[j]的概率
枚举翻转[l,r]转移:
1>l<=i<=r<j f[l+r-i][j][k-1]
2>i<l<=j<=r f[i][l+r-j][k-1]
3>l<=i<j<=r f[l+r-i][l+r-j][k-1]
显然第一种和第二种的转移点是O(n)的
第三种一二维距离不变也是O(n)的
推一推式子便可以做到O(1)转移
T2
设f[i][j]代表到i选了j个的最大权值
f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]*j)
可以证明转移具有决策单调性
用平衡树维护f的差分数组即可
T3
问题简化为求所以小的面积的和
大的显然可以O(1)得到
考虑枚举一个端点
找到分界点后通过原先预处理的前缀面积和和前缀前缀和来O(1)计算
复杂度O(n)
最后简单说一下考试思路
写题顺序213
前两天考的特别差，都是因为简单题A不了导致了
所以今天的考试中一直想要切掉某一道题
但是最后以失败告终
T1没想到期望的可加性，不该出现这样的问题啊
原来可是做过好多通过可加性简化问题的
T2dp式子不一样根本不可能想到优化
以后考试要注意在无法优化的情况下大胆尝试其他dp式子来寻找灵感
T3思路和正解一样但是不会用原点来求任意端点组成的面积
只会先固定一个凸包上的点来求，所以退化成了O(n^2)