雨下整夜

楼房重建傻了，现在才知道这个静态问题是可以 1log 的。

先找到区间中最大值的位置 $p$，那么 $[l,p]$ 内的 $i$ 只需要考虑前缀 $\max$，$[p+1,r]$ 内的 $i$ 只需要考虑后缀 $\max$。以前缀 $\max$ 为例。我们要求一个区间 $[l,r]$ 内的 $\sum\limits_{i=l}^r\max\{0,\min\{H,\max_{j=l}^r h_j\}-h_i\}$。

可以二分出区间中第一个 $>H$ 的位置 $x$。再次将问题分为 $[l,x-1]$ 和 $[x,r]$ 两部分。

第一部分的贡献为 $\sum\limits_{i=l}^{x-1}\max_{j=l}^ih_j-\sum\limits_{i=l}^{x-1}h_i$。后者容易前缀和维护。前者是区间前缀 $\max$ 和，我一开始只会单侧递归，但事实上有一个高妙做法。用单调栈记录每个位置的后继，那么对于一个区间 $[l,r]$，从 $l$ 开始不断跳到当前位置的后继，可以得到前缀 $\max$ 序列。那么就可以暴力计算每种前缀 $\max$ 的贡献。考虑优化，可以发现除了最后一个前缀 $\max$，其余所有前缀 $\max$ 贡献的范围都是它到后继之间，可以提前预处理出来。那么就是边跳边累计贡献，用倍增优化这个过程即可。最后一个前缀 $\max$ 再单独算一下即可。

第二部分的贡献为 $\sum\limits_{i=x}^r\max\{0,H-h_i\}$。是一个二维偏序的形式，主席树维护即可。

认为 $n,q$ 同阶，时空复杂度 $\mathcal{O}(n\log n)$。