https://ac.nowcoder.com/acm/problem/15815 首先暴力枚举每一个区间必定是超时的。那么考虑每个点对于答案的贡献值,可以这样想,对于点h[i]作为最大值在多少个区间出现,作为最小值在多少个区间出现?这个点对于答案的贡献就是h[i]*作为最大值出现的次数 - h[i]*作为最小值出现的次数,对于每个点,求一下贡献累加即可。 求每个点贡献的过程用单调栈来维护,拿求最大值的次数来举例。对于点i,找到左端第一个比h[i]大的数,记其位置为L,找到右端第一个比h[i]大的数,记其位置为…