一，悬线法

分别从小到大和从大到小递推 $l_i$,$r_i$ 表示 $i$ 往左往右最远能到哪个点，由于具有传递性，可以使 $l_i=l_{l_i-1}$，可以证明时间复杂度 $O(n)$。

二，单调栈

若 $a_i>a_{i+1}$，则 $a_i$ 超过的那部分完全没用，故将 $i$ 与 $i+1$ 合并，更新宽度计算答案。

三，笛卡尔树

以下标和权值为关键字建树，记录权值乘以子树大小的最大值。

四，说一下悬线法与单调栈。

悬线法：类似 $dp$，大多情况下也能用单调栈解。

单调栈：由于后面的答案一定不能恰好延伸到违反单调性的点（不在单调栈中的点），将有单调性的点（在单调栈中的点）与前面没有单调性的点的贡献合并（在本题中是宽度）。