P7220 [JOISC 2020] 掃除

JOISC2020 Day 1 T3 由于数据点较多，本题只评测其中的部分数据。 希望获得完整数据的可以到[这里](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day1/sweeping-data.zip)自行下载。

由于 Bitaro AK 了 IOI，所以 IOI 主办方送了他一套房子，为一个边长为 $N$ 的等腰直角三角形。房间内一点用坐标 $(x,y)$ 表示，其中 $0\leq x+y\leq N$。直角顶点为原点，三角形两腰分别为 $x$ 轴与 $y$ 轴。  一天，Bitaro 发现自己已经 AK 了 1919810 届 IOI 闲的没事做准备打扫房间里的灰尘。这些灰尘一开始一共有 $M$ 堆，其中第 $i$ 堆位于 $(X_i,Y_i)$。同时，可能存在多堆灰尘位于同一个位置上的情况。 现在 Bitaro 准备用扫帚打扫房间。我们认为扫帚是放置在房间里的一条线段，并且将这条线段的长度称为扫帚的宽度。由于 Bitaro 很有条理，所以他只会用以下的两种方式打扫房间： - Bitaro 将扫帚平行于 $y$ 轴放置，一端位于原点。然后他会垂直向右移动扫帚，直到不能移动为止。如果扫帚的宽度为 $l$，那么原来一堆满足 $x

无

无

### 样例 1 解释 一开始第一堆灰尘位于 $(1,1)$，第二堆灰尘位于 $(4,0)$。图一描述了房间现在的情况。  在第一个事件中，添加了 $(2,3)$ 位置上的第三堆灰尘。图二描述了房间现在的情况。  在第二个事件中，Bitaro 用宽度为 $3$ 的扫帚进行了过程 V。之后，第一堆灰尘移动到了 $(1,3)$，图三描述了房间现在的情况。  在第三个事件中，Bitaro 计算了第一堆灰尘的坐标 $(1,3)$。 在第四个事件中，添加 $(1,2)$ 位置上的第四堆灰尘。图四描述了房间现在的情况。  在第五个事件中，Bitaro 用宽度为 $3$ 的扫帚进行了过程 H，第一堆灰尘移到了 $(3,3)$，第三堆灰尘移到了 $(3,3)$，第四堆灰尘移到了 $(3,2)$。图五描述了房间现在的情况。  在第六个事件中，Bitaro 用宽度为 $0$ 的扫帚进行了过程 H，第二堆灰尘移到了 $(6,0)$。图六描述了房间现在的情况。  在第七个事件中，Bitaro 计算了第四堆灰尘的坐标 $(3,2)$。 在第八个事件中，Bitaro 用宽度为 $2$ 的扫帚进行了过程 V，然而什么都没有发生。图七描述了房间现在的情况。  在第九个事件中，Bitaro 计算了第三堆灰尘的坐标 $(3,3)$。 在第十个事件中，Bitaro 计算了第二堆灰尘的坐标 $(6,0)$。 这组样例满足子任务 1 和子任务 5 的限制。 #### 样例 2~5 解释 第二组样例满足子任务 1,2,4,5 的限制。 第三组样例满足子任务 1,2,5 的限制。 第四组样例满足子任务 1,3,4,5 的限制。 第五组样例满足子任务 1,5 的限制。 #### 子任务 | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | Subtask 1 | $m\leq 2\times 10^3,Q\leq 5\times 10^3$ | $1$ | | Subtask 2 | $T\in\{1,2,4\}$ | $10$ | | Subtask 3 | $T\in\{1,2,3\},X_i\leq X_{i+1},Y_i\geq Y_{i+1}(1\leq i\leq m-1)$ | $11$ | | Subtask 4 | $T\in\{1,2,3\}$ | $53$ | | Subtask 5 | 无 | $25$ | 对于 $100\%$ 的数据，$1\leq n\leq 10^9,1\leq m\leq 5\times 10^5,1\leq Q\leq 10^6$。保证： - $0\leq X_i,Y_i\leq N,X_i+Y_i\leq N(1\leq i\leq m)$； - $1\leq P_i\leq M^\prime(1\leq i\leq Q)$，其中 $M^\prime$ 表示事件 $i$ 发生时灰尘的堆数； - $0\leq L_i\leq n-1(1\leq i\leq Q)$； - $0\leq A_i,B_i\leq n,A_i+B_i\leq n(1\leq i\leq Q)$； - 至少存在一个 $T_i=1$ 的事件。