BZOJ3745:[Coci2015]Norma

题目传送门

首先考虑暴力,复杂度O(N^2)。

题目叫我们求

即对于任意区间求区间长度乘以区间最小值乘以区间最大值的总和。

 

考虑CDQ分治。

设我们当前分治到的区间为,有

倒序枚举,同时记录表示中的最小值大于的最小值的最右边,表示中的最大值小于的最大值的最右边,的最大值,的最小值。

 

考虑下面这些情况(令):

1.

​ 直接等差数列公式即可。

 

2.

​ 这预处理出即可。

 

3.

​ 预处理出,

即可

 

Code: