题意：

• 给一数组a，可对其中 a i a_i ai​进行如下操作：将 a i a_i ai​拆成两数之和，然后代替 a i a_i ai​加入数组中。设一个数组的 e x t r e m e extreme extreme v a l u e value value 指的是：使得数组单调不下降的最小操作次数。据此，求a数组的所有子数组的 e x t r e m e extreme extreme v a l u e value value 之和

思路：

• 先考虑一个数组，显然，将末尾元素拆分是没有意义的，且会使答案增大。而对于中间元素，例如 . . . [ 17 ] , 5 , 10 , 23 , . . . ... [17], 5, 10, 23, ... ...[17],5,10,23,... ，如果它违反了单调不下降的规则，就必须进行拆分，可以有多种拆法，但使得其中最小元素尽可能大，是最优的拆法。例如，拆成 ( 4 , 4 , 4 , 5 ) (4, 4, 4, 5) (4,4,4,5)比 ( 3 , 3 , 3 , 3 , 5 ) (3, 3, 3, 3, 5) (3,3,3,3,5)更好，因为这可能减少前面需要的操作数量，因此，相当于让拆分成的元素尽可能接近，且数量尽可能少，又要让其中最大的小于 a i + 1 a_{i+1} ai+1​，那么，对于当前的数 a i a_i ai​和下一个数 a i + 1 < a i a_{i+1}<a_i ai+1​<ai​，我们应当拆分，例如这里17应当分为 ⌈ 17 / 5 ⌉ = 4 \lceil 17/5 \rceil = 4 ⌈17/5⌉=4个数，所以最小数是 ⌊ 17 / 4 ⌋ = 4 \lfloor 17/4 \rfloor = 4 ⌊17/4⌋=4。显然，如果 a i a_i ai​比 a i + 1 a_{i+1} ai+1​小，则认为我们将它“拆分成一个数”
• 这样扫一遍下来，以 O ( n ) O(n) O(n)解决了求解单个数组的问题，但是，子数组的数量是 n 2 n^2 n2数量级，不能全部这样求解
• 考虑 d p i , x dp_{i,x} dpi,x​是第 i i i个数被拆分成最小元素为 x x x的若干个数，并且以 x x x开头的非递减数列的数量。有 d p i − 1 , y dp_{i-1,y} dpi−1,y​ += d p i , x dp_{i,x} dpi,x​，因此可以转化。
• 一个数 n n n拆分为最小元素 x x x ∈ \in ∈ { n n n, ⌊ n / 2 ⌋ \lfloor {n/2} \rfloor ⌊n/2⌋, ⌊ n / 3 ⌋ \lfloor {n/3} \rfloor ⌊n/3⌋,…, 1 1 1}，这个集合中元素个数不是n个，而是 O ( n 1 / 2 ) O(n^{1/2}) O(n1/2)数量级的，这一点在整除分块的技巧中也有使用。
• 最终我们根据 d p dp dp数组统计答案。对于 d p i + 1 , x dp{i+1,x} dpi+1,x，它对答案的贡献是 i ∗ d p i + 1 , x ∗ ( ⌈ a i / a i + 1 ⌉ − 1 ) i * dp_{i+1,x} * (\lceil a_i / a_{i+1} \rceil - 1) i∗dpi+1,x​∗(⌈ai​/ai+1​⌉−1)，这是因为有 i ∗ d p i + 1 , x i * dp_{i+1,x} i∗dpi+1,x​个数列，每个数列对 a i a_i ai​执行这样的拆分