4101 OIL

题面

内容

给你一个长为 $n$ 的序列 $a$。

定义 $\operatorname{maxpre}(l,r)$ 是区间 $[l,r]$ 的最大前缀和, 即 $\max \sum\limits_{j=l}^ia_j,i\in[l-1,r]$。

定义 $\operatorname{maxsuf}(l,r)$ 是区间 $[l,r]$ 的最大后缀和, 即 $\max \sum\limits_{j=i}^ra_j,i\in[l,r+1]$。

最大前缀与最大后缀都可以是空串。

求：

$\sum\limits_{l=1}^n\sum\limits_{r=l+1}^n\sum\limits_{i=l}^{r-1}\operatorname{maxpre}(l,i)\operatorname{maxsuf}(i+1,r)$

输出答案对 $10^9+7$ 取模的结果。

输入

第一行一个数 $n$ 表示这个序列的长度。

之后一行包含 $n$ 个整数，表示这个序列。

保证序列中所有元素都在 $[-10^9,10^9]$ 中。

输出

输出一行一个整数表示答案。

样例1

输入

3
1 -2 3

输出

6

样例2

输入

5
1 -2 3 -4 5

输出

76

思路

不能枚举区间，

i为分界点，

以i开始的前缀和以i结束的后缀区间，

两两组合成的区间，

左边对应最大前缀，

右边对应最大后缀，

只需要把左边的所有最大前缀和右边的最大后缀的和乘起来，

求的时候就需要从前往后枚举一遍，边求前缀和边取max，

维护一个集合S，

S中：维护当前区间除去最大前缀的和，

那么这个东西大于0就需要更新，

那么i变为i+1后，每个元素都$+=a[i+1]$。

第二个操作：

找出所有x，y>0，

修改为x+y,0，

每次插入则修改全局标记，

插入的数要减去当前的tag，

tag要加上当前插入的数，

一开始它们的最大前缀是不一样的，

只要后缀被更新一次，那么00就不会再不同，那么就0可以合并区间，

合并以后y的和就可以知道了，

其实就开一个临时变量，然后扫的过程中把最大前缀和的总和记录下来就可以了，

记录一下已经合并的区间的数量，

这样正着扫一遍，倒着扫一遍，然后两个乘起来就可以了。