T1
这个式子看一下可以发现是这样子的：
[dp[i]=minlimits_{j=1}^{i-1}{dp[j]+a[i]-frac{(i-j)(i-j-1)}{2}}
]
发现这个东西可以用斜率优化。
但是要求(a_i)递增。
那么直接用线段树维护凸包就可以了。
维护每个区间的答案。
单点修改的话修改(logn)个区间。
查询用二分凸包，复杂度是(O(nlog^2n))的。
T2
这个搜索题其实特别恶心。。。
用一个(dp)来算出当前某个位置确定了的答案。
然后乘上排列就行了。
注意要先把(k)压缩到一个较小的量级然后(dp)。
T3
这个题的话其实没啥
但是有一个非常有趣的结论。
如果两个相邻的组之间某一位置(j)是不一样的。
那么其后面的位置一定是最大排列和最小排列。
然后做一个(n^2)的(dp)，用组合数来计算贡献就可以做到(O(n))了。