这题乍一看不太好做，当时还想了单调栈或改变枚举顺序之类的做法，但都不可做
但仔细一想，我们发现答案的\(b_l\)和\(b_r\)一定会被选到，否则我们可以把没用的部分去掉，这样\(b_1+b_2+b_3\)的值不会变，\(r-l\)还会变小，这一步是缩小答案的范围
然后我们发现这个条件还是很严格，因为我们没法保证\(b_l\)和\(b_r\)和\((l,r)\)内的一个数恰好就是这个区间\([l,r]\)的前三大值
但我们发现我们没必要总是取到这个条件，我们考虑把一定不对的答案也加入可能的答案的集合中。我们枚举一个\(i\)，表示\(b_i\)一定选到，则可以确定\(l\)可能的范围为\([1,i)\)，同样的，\(r \in (i,n]\)，这样我们可以求出前缀最大的\(b_l+l\)和后缀最大的\(b_r-r\)，分别记作\(pre_i\)和\(suf_i\)，然后可以直接用\(b_i+pre_{i-1}+suf_{i+1}\)来更新答案
为什么这样一定是对的呢，因为发现如果\(b_i\)并不是\([l,r]\)的最大值，不妨设\([l,r]\)的最大值为\(b_j\)，则当\(i\)枚举到\(j\)的时候显然会再把正确的答案算一遍，而这个答案显然是不劣于上一个答案的，因此即使我们加入了错误的限制也无妨
最终复杂度\(O(n)\)
标签：pre,suf,枚举,答案,我们,CF1826D From： https://www.cnblogs.com/fox-konata/p/17663175.html