【时光倒流】P15940 [JOI Final 2026] 花园 3 / Garden 3 笔记

数据结构复健。

由于四个方向的边界对称，只需考虑 $x_{\min }$ 即可。

容易发现 $x_{\min }$ 越来越小，暴力贪心是每次从当前答案往左扫，时间复杂度平方级。

出现这样的问题是因为检验不是连续的，每次都不知道新的答案能往左扩展到哪里，这样并没有很好地利用“越来越小”这个性质。

因此直接时光倒流，这样子 $x_{\min }$ 越来越大，并且只要这一行都没有符合要求的，就可以直接推到下一行。

转换为指针扫描的一维为 $x$ 和时间，线段树维护一维为 $y$ 的双指针扫描线问题，实现时需要用 $\mathrm{vis}$ 数组记录防止反复往线段树内贡献。