题目大意
有一个长度为 nnn 的数组 aaa ，判断是否所有区间 [i,j][i,j][i,j] 满足 max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i,a_{i+1},\dots,a_{j-1},a_j)\geq a_i+a_{i+1}+\dots +a_{j-1}+a_jmax(ai ,ai+1 ,…,aj−1 ,aj )≥ai +ai+1 +⋯+aj−1 +aj 。
解题思路
我们考虑对于每一个位置 iii ，如果这个位置的数是区间最大值，首先找出所有满足这个数为最大值的区间，这部分我们可以用单调栈求出左边和右边第一个大于这个数的位置 LiL_iLi 和 RiR_iRi ，时间复杂度是 O(n)O(n)O(n) 线性的。
然后对于每一个位置 iii ，在区间 [Li,Ri][L_i,R_i][Li ,Ri ] 中，如果最大的区间和比这个数还要小的话，那么这个位置就是满足条件的。在找最大区间和时，需要注意，由于位置 iii 一定需要在区间中，所以我们需要在 [i,Ri−1][i,R_i-1][i,Ri −1] 中找到最大前缀和 mxsmxsmxs ，在 [Li,i−1][L_i,i-1][Li ,i−1] 中找到最小前缀和 mismismis ，区间 [Li,Ri][L_i,R_i][Li ,Ri ] 中的最大区间和就是 mxs−mismxs-mismxs−mis 。
可以用 ststst 表或者线段树快速查询区间最大最小前缀和。
时间复杂度 O(nlogn)O(nlogn)O(nlogn) 。
参考代码
