T2

dp[k]表示把前k个分成若干组，这时候他后面都已经加上了，应该多加的数。

就是dp[k]=ans_k+x(组数)*sum_ans(k+1,n);

dp[k]->dp[i]

Ask（l，r）代表l到r的最大值减去最小值 用st搞出来

Ans_sum/sum_ans都代表前缀和

Cost（l,r）代表l到r的ask+sum。

方法一：数学推导

Dp[k]=ans_k+x(组数)*sum_ans(i+1,n)+x*sum_ans(k+1,i);

Dp[i]=ans_i+ans_sum(i+1,n)*(x+1)

=ans_k+ans_sum(k+1,i)*(x+1)+ask(k+1,i)+ans_sum(i+1,n)*(x+1)

=dp[k]+ans_sum(k+1,i)+ask(k+1,i)+ans_sum(i+1,n)

=dp[k]+cost(k+1,i)+ans_sum(i+1,n);

方法二：

瞪眼法

多加了cost（k+1,i）

更新后面+sum_ans（i+1，n）；

dp[i]=dp[k]+sum_ans(i+1,n)+cost(k+1,i);

 优化 n*logn

实际上就是在找min（dp[k]+cost(k+1,i)）+一个定值。

Cost非递减，dp要是再增，肯定不行

从i-1开始维护一个dp是递减的序列。

A了