【题解】P9061

· · 题解

以下认为 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 + 线段树实现。

代码暂时咕咕咕。