题解：P12587 「KTSC 2019 R2」外星仙人掌

xuanxuan001 · 2025-05-22 20:47:46 · 题解

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

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

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

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

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