最近在逛一亩三分地正津津有味看着大家对Gu的讨论，突然这时候看到一篇帖子是求助一道亚麻的OA算法面试题，虽然没在找工作但是每天还是会一直刷leetcode和看系统设计保持最佳状态，当时想着就当今天加训了，然后读完题想想很简单的题目嘛,然后看到数据量时候我瞬间傻了....

题目：

题目意思非常简单，给你一个数组，求出所有子数组的权重和，权重是每个子数组中的最小值，看例子也非常容易理解题意。

数据量：0=n=8*10^5

思路：

1、这道题最朴素的解法就是枚举每一个子数组，然后对每一个子数组求和，找最小值。如果不加任何优化直接暴力求解的话枚举子数组需要O(N^2)时间复杂度，然后求和找最小值还需要O(N)时间复杂度，所以总体需要O(N^3)时间复杂度，基于这个数据量肯定TLE。

2、那么有没有办法优化呢？办法有很多，如果leetcode刷得比较多会发现这题和LC很相似，可以用LC的解法求出power数组中每一个元素作为最小值在数组中的范围，然后枚举每一个power[i]配上和prefixsum就可以了，这样的话使用monotonicstack+prefixsum可以在O(1)时间复杂度查询每个子数组的min和sum,但是枚举子数组还是需要O(N^2)的时间复杂度，所以总体时间复杂度还是O(N^2)时间复杂度，基于这个数据量肯定TLE。

------------------------------------------------------------------------------

当时看完题的第一反应就是第二种解法，这种解法基本就是一个mid难度，中规中矩，但是说实话LC通过率也只有32%。

当然还有更多骚操作比如使用线段树，可以降到nlogn，但是也有可能TLE，于是我就陷入沉思，草稿纸拿出来开始画来画去。

-----------------------------------------------------------------------------

所以这道题很明确了，这个数据量必须是O(N)时间复杂度才能过，那么就肯定不能去枚举子数组了，就需要用更极限的方法了，于是我又开始重新思考了LC这道题，因为这两题实在太相似了。

重新思考下这道题发现有几个关键点：

1、这道题最后的答案其实就等于每一个power[i]*power[i]作为最小值的子数组的和，根据分配律我们可以发现其实就是每一个power[i]作为最小值所能辐射到的范围内所有子数组的和*power[i]，这样说确实很抽象来看一个例子。

对于[2,3,1,2]对于这个数组power[2]也就是1这个数组作为最小值可以辐射到的范围是[-1,3]，也就是说对于1这个数字来说它对答案最后的贡献值就等于

1*sum[0,2]+1*sum[0,3]+1*sum[1,2]+1*sum[1,3]+1*sum[2,3]+1*sum[2,2]

根据分配律我们可以改写成1*(sum[0,2]+sum[0,3]+sum[1,2]+sum[1,3].........)=(1*辐射范围内子数组的和)

那么这样我们就能发现我们只需要求出:

Q1)每一个power[i]最为最小值的辐射范围是什么?

Q2)如何在O(1)时间复杂度求出每一个范围内以power[i]作为最小值的所有子数组的和？

这样我们就可以在O(N)时间复杂度完成这道题。

对于Q1就和LC一模一样，