自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 23:16:37，当前版本为作者最后更新于2025-05-22 20:47:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

确实比较板，做出来没花太多时间，但韩国？ 2019 年？放在 D2T2？强度有点高吧（还是我做复杂了，感觉我的做法能支持区间修改）。

考虑求出水加仙人掌的总体积后再减去仙人掌的部分，那么每个位置的高度其实就是前缀 $\max$ 和后缀 $\max$ 的较小值。这样腹背受敌同时考虑两边的信息还是太复杂了，但发现其中有一个是全局 $\max$，所以重要的其实就是另一个的值。

因此可以找出全局 $\max$ 的位置，然后将两边分开考虑，以左边为例，发现其实就是前缀 $\max$ 和，这个用楼房重建就可以做，复杂度 $O((n+q)\log^2 n)$，可以通过。

如果不强制在线的话其实可以离线然后按位置扫描线并用吉司机线段树维护所有询问的状态做到单 $\log$ 的（似乎所有的楼房重建问题都可以这样离线做），但它强制在线。

感觉不太需要放代码了，照着写就行。