5733. 阴影映射

单点时限: 1.0 sec

内存限制: 512 MB

实时阴影是电子游戏中最为重要的画面效果之一。在计算机图形学中,通常使用阴影映射方法来实现实时阴影。

游戏开发部正在开发一款 2D 游戏,同时希望能够在 2D 游戏中模仿 3D 游戏的光影效果,请帮帮游戏开发部!

给定 x-y 平面上的 $n$ 个矩形,矩形的边界平行于坐标轴,且可能相互重叠。同时给定点光源的坐标。现有 $m$ 次操作,每次操作添加或删除一个矩形,或询问 $x$ 轴上的一点是否在阴影内。

输入格式

第一行,两个整数 $n, m (1\leq n, m \leq 2\times 10^5)$。
第二行,两个整数 $l_x, l_y$,表示光源的坐标为 $(l_x, l_y)$。$|l_x|\leq 2\times 10^5, 0 < l_y\leq 2\times 10^5$。
接下来 $n$ 行,每行 $5$ 个整数 $id, x, y, w, h$,表示编号为 $id$ 的矩形,左下角坐标为 $(x, y)$,宽为 $w$,高为 $h$。
接下来 $m$ 行,每行先输入一个正整数 $opt\in [1, 3]$。

  • 若 $opt = 1$,则接下来输入 $5$ 个整数 $id, x, y, w, h$,表示增加一个编号为 $id$,且左下角坐标为 $(x, y)$,宽和高为 $w$ 和 $h$ 的矩形。
  • 若 $opt = 2$,则接下来输入一个整数 $id$,表示删除编号为 $id$ 的矩形。
  • 若 $opt = 3$,则接下来输入一个整数 $p$,表示查询坐标 $(p, 0)$ 是否在阴影中。

$1 \leq id \leq 4\times 10^5$
$|x|\leq 2\times 10^5, 0 < y \leq 2\times 10^5$
$0 < w, h \leq 2\times 10^5$
$|p| \leq 10^9$
保证任意时刻场景中所有矩形的 $id$ 互不相同。保证所有矩形各个顶点的 $y$ 坐标一定严格小于光源的 $y$ 坐标。若询问点在阴影的边界上,仍算作在阴影内。

输出格式

对于每个 $opt = 3$ 的询问,若询问的点在阴影中,则输出一行 YES,否则输出一行 NO

样例

Input
3 19
4 7
1 1 1 2 1
2 6 1 2 3
3 5 2 4 1
3 -1
3 0
3 2
3 3
3 4
3 5
3 6
3 12
3 13
3 14
1 4 4 5 2 1
3 3
3 4
3 5
3 18
3 19
2 1
3 2
3 3
Output
NO
YES
YES
NO
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO

提示

在进行所有修改操作之前,所有矩形的位置如下 (绿色部分为阴影区域):
002.png
在加入一个矩形后,所有矩形的位置如下:
003.png
在删除一个矩形后,所有矩形的位置如下:
004.png

14 人解决,20 人已尝试。

15 份提交通过,共有 78 份提交。

5.7 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 3 月,2 周前.

来源: N/A

题目标签