「题解搬运」影魔

做法很多。
有些题解写的非常恶心，叫人看得一脸懵逼，只记录两个较好的解法。
关键都在于搞清楚要计算的对象，把握好计算的时机。

1. 发现两种贡献的产生方式都有一个共同的特点，
   产生贡献的点对围成的区间中，最大值一定在区间端点上。
   我们需要关注的焦点，就在于“最值分布在区间端点”这个事情上。

再观察，可以产生贡献分为三种。
次高，低，高
低，次高，高
高，次高，低
进一步发现第一种贡献，只有\(O(n)\)项，可以直接单调栈跑出来。
第二种贡献还含有两个要素，一个是最值，一个是次大值。
那么考虑确定了最值和次大值位置时，哪些位置可以与最值形成点对产生贡献。
以低，次高，高为例，那么次高以左直到第一个比次高要高的位置的所有位置都可以

考虑什么东西可以维护一个位置以左第一个比它要高的位置的距离
单调栈。
于是以低，次高，高为例，维护一个单调递减的单调栈，
设新加入元素为ntop高于栈顶s[top]要弹栈，则
s[top]到s[top-1]之间的所有点 与 s[top] 与 ntop
可以形成斜坡状贡献，给这个区间进行区间累加即可。
区间累加后，在扫完第i个元素时，第j个位置的值表示
j与满足h[j]<h[k]&&k<=i的所有k形成贡献的和
那么我们这一轮要统计的答案就是区间求和的答案。
区间求和的范围限制了子区间的左端点，
此时只枚举到i限制了子区间的右端点，
如此保证了不重不漏地统计了所有子区间，反过来再做一边即可。

依据了第二种贡献呈斜坡状的性质，
使用了把贡献累加到左端点所在位置上的技巧，
在最右侧统计答案，此时右端点该给左端点累加的东西都累加完毕了。

1. 运用了一个非常巨的差分手法。
   考虑把那三种贡献分成两类，
   \(L_i -> R_i\)
   \(L_i -> [i+1,R_i-1]\)
   \(R_i -> [L_i+1,i-1]\)
   两类分别计算，其中第三项即是运用上一解法的手法。
   考虑前两种，我们希望得到的是区间左端点以右的\(L_i\)累加的贡献
   然而枚举到右端点时，左端点以左的贡献还是累加进去了，令人心碎。

减掉不就好辣！
在\(LeftEdge\)处就检查一遍此时\([LeftEdge,RightEdge]\)的贡献和
用\(RightEdge\)处求出的贡献和把它减了就行了。

同时还发现由于统计时只枚举到\(RightEdge\)
以右的非法贡献还没有被累加
而且在\(LeftEdge-1\)处时，\(RightEdge\)以右的贡献更不可能被累加。
所以对于第三项贡献，可以和前两项同时累加，毕竟差分相减时只是一个\(0-0=0\)。

再次从二维（扫描线）的角度理解这个差分！
以L为横坐标，R为右坐标建系，可以看作把贡献累加在二维平面上的点上。
为了更方便一点，我们把横向的答案和纵向的用同一棵线段树维护了
（就是上一段最后一行所说的事）
而且同一组\(L_i,R_i\)的三种贡献正好组成了一个直角，像一个矩形的左上角。

我们要求和的贡献，是二维平面上一个正方形，
这个正方形有个特点就是横坐标所在区间和纵坐标所在区间重合。（废话都是同一询问区间的子区间）
算了放个图。

「题解搬运」影魔

原文：https://www.cnblogs.com/yxsplayxs/p/12046115.html