我T2被卡常。
（笑。
T1
这个题和那个ZJOI线段树挺像的。
利用期望的线性性，dp出每一对点成为逆序对的概率。
然后加起来就是答案了。
这样直接dp是(O(n^4k))的。
做两个前缀和就可以做到(O(n^2k))了。
T2
打个表能发现决策如果在(i)可行，那么在(i+1)也可行。
证明的话考虑
选(i)个的话，选更优秀的余地显然比选(i+1)个要大。
如果(i)个都合适了，那么(i+1)一定也合适。
写一个(dp)式子。
就发现可以用(splay)搞区间平移和区间加等差数列。
卡卡常就过了。
T3
这么水的题我竟然不会。。
思维僵化了。
维护几个前缀和和叉积前缀和就行了。。。
叉积前缀和为了统计答案做两次就可以了。
要是说失误的话。
就是T2写很久但是被卡常，T3没想的太深就随便打了个暴力。