题意描述：
定义一个序列的权值为一段前缀与一段子段，满足要么前缀与子段不交，要么完全包含的和的最大值，给定一个序列 \(a\)，求 \(a\) 的所有子区间的权值和
\(n\le 10^6\)
发现如果前缀与子段有交且不包含，那么一定不优，因为子段未被包含的一段一定是正的，不然就不是最大子段了
因此可以把问题拆成两部分：所有子区间的最大前缀以及所有子区间的最大子段和
第一部分是 trivial 的，直接用单调栈或笛卡尔树求出贡献范围即可
第二部分显然考虑分治，对于跨过中点的区间的贡献，可以分成三种情况（即线段树求最大子段和的三种）
我们设 \(dp_l\) （\(dp_r\)） 表示从中点至左边（右边） \(l\) （\(r\)）位置的最大子段和，\(sum_l\) （\(sum_r\)）为最大前缀和
在从中点向左扫的过程中，首先 \(dp_l,sum_l\) 肯定是单调不降的，而 \(dp_l-sum_l\) 也是单调不降的，因为 \(dp_l\ge sum_l\)，而新加入一个元素能贡献到 \(sum_l\) 那么也一定能贡献到 \(dp_l\)，否则也有可能贡献到 \(dp_l\)，所以差距不会变小，讨论一下三种情况的大小关系：
- \(dp_l>max(dp_r,sum_l+sum_r)\)，拆成 \(dp_l>dp_r\) 和 \(dp_l>sum_l+sum_r\)，移项得 \(dp_l-sum_l>sum_r\)，因此取到这种情况的分界点 \(r\) 一定单调不降
- \(dp_r>max(dp_l,sum_l+sum_r)\)，类似上一种，\(dp_r-sum_r>sum_l\)，随着 \(l\) 的移动，可能的位置会越来越少
- \(sum_l+sum_r>max(dp_l+dp_r)\)，拆开移项得 \(sum_l>dp_r-sum_r,sum_r>dp_l-sum_l\)，那么这种情况的分界点是不断向后移动的
于是贡献分成三段，第一段显然是 \(dp_l\)，第三段显然是 \(dp_r\)，那么中间就是 \(sum_l+sum_r\) 了，直接前缀和维护
一个直观的理解：\(dp_l\) 越来越大，在右边比较短的时候没必要取右边一点点大的地方，但当右边比较大的时候，就可以把两边拼起来，右边非常大的时候，由于这时 \(dp_r\) 与 \(sum_r\) 的差距已经很大了，算上左边的 \(sum_l\) 也无济于事
时间复杂度 \(O(n\log n)\)
标签：CF1787I,前缀,子段,题解,sum,Treasure,右边,贡献,dp From： https://www.cnblogs.com/pidan123/p/17098299.html