雨下整夜

lzyqwq · 2025-11-21 15:51:24 · 题解

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

给出长度为 n 的序列 h_1,\dots,h_n，q 次询问 l,r,H，求 \sum\limits_{i=l}^r\max\{0,\min\{H,\max_{j=l}^ih_j,\max_{j=i}^rh_j\}-h_i\}。强制在线。

先找到区间中最大值的位置 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)。