自动搬运

查看原文

来自洛谷，原作者为

	Renshey 滚落沙尘，泛生浮光。掠影千年，奔走四方。

搬运于2025-08-24 22:45:01，当前版本为作者最后更新于2023-02-11 12:56:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

以下认为 $n, m$ 同阶。

考虑修改的性质。以 $o = 1$ 为例，一次修改 $x, y$ 相当于清空了 $(x, y - 1)$ 左下方的所有点。找出所有修改的轮廓线后，所有的点要么在轮廓线上，要么在轮廓线右上方，且右上方的点均为未被移动过的点。求出每个点进入轮廓线的时间是二维偏序，可以直接预处理计算。

考虑如何计算答案。轮廓线上有贡献的点是一段区间，具体维护方式后文会详细阐述；计算轮廓线外有贡献的点是坐标与时间的三维偏序，可以在 $O(n\log^2 n)$ 的时间复杂度内解决，显然无法通过。

由于轮廓线具有良好的性质，可以考虑根据轮廓线来进行计算。如果询问点在轮廓线的左下方显然答案为 $0$。否则由于轮廓线的单调性，询问点的右上方一定与轮廓线无交。于是统计右上方的点数不再需要时间维的限制，可以二维偏序解决。只需要通过简单容斥即可计算出左下方的点数。容斥时需要计算某一侧的点数，减少了一维坐标限制，同样可以二维偏序解决。如果可以在 $O(n \log n)$ 的时间复杂度内对轮廓线上的点进行维护，即可在 $O(n \log n)$ 的时间复杂度内完成本题。

维护轮廓线上的点有两种方式：

方式一

注意到轮廓线上的点的相对顺序不会再改变，且 $x-y$ 是单调的，所以可以直接用平衡树进行维护。修改时需要插入若干个单点，将某一个区间的 $x, y$ 进行覆盖；查询时需要询问一个区间的点数。这些操作都可以在平衡树上解决。

由于平衡树的常数较大，需要卡常才能够通过。

代码

评测记录

方式二

将轮廓线上的点按最后一次移动操作的类型分类，形成若干条横线段与竖线段。则每次修改需要合并若干条线段，查询时需要找到一个区间的线段。以上操作全部可以通过 set + 线段树实现。

代码暂时咕咕咕。