---

题目描述

题目译自 2021년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「렉」

在一台老旧的电脑上使用画图工具。画图工具的屏幕是一个由像素组成的网格。最左下角的像素坐标是 $(1,1)$，向右和向上分别是第 $a$ 和第 $b$ 个像素的坐标为 $(a, b)$。初始屏幕上绘制了 $N$ 个垂直和水平边的矩形。矩形由包含在该区域内的像素表示。

将对这 $N$ 个矩形执行 $M$ 个移动命令。矩形可以向东、西、南、北四个方向移动，也可以向东北、西北、东南、西南（与水平轴成 $45$ 度方向）四个方向移动。此外，还给出了移动距离 $d$。换句话说，移动命令由方向和距离组成。具体来说，如果矩形的最左下角像素坐标是 $(a, b)$，那么向东、北、西、南方向移动距离 $d$ 后，最左下角像素的坐标分别为 $(a+d, b)$、$(a, b+d)$、$(a-d, b)$、$(a, b-d)$。向东北、西北、东南、西南方向移动距离 $d$ 后，最左下角像素的坐标分别为 $(a+d, b+d)$、$(a-d, b+d)$、$(a-d, b-d)$、$(a+d, b-d)$（见图 1）。

图 1

在屏幕上，矩形 $R$ 移动距离 $d$ 时，每移动 $1$ 个单位距离，都会快速显示 $R$ 的新位置。然而，由于我们的电脑非常老旧，移动 $R$ 时会出现严重的卡顿。结果是，$R$ 移动过程中所有经过的位置都会保留在屏幕上。因此，当 $R$ 移动距离 $d$ 时，屏幕上会新增 $d$ 个矩形。例如，在图 2 中，矩形向东北方向移动距离 $3$ 时，会新增 $3$ 个矩形，总共在屏幕上留下 $4$ 个矩形。移动后，位于东北方向最远处的矩形就是 $R$。

图 2

执行完 $M$ 个移动命令后，会有 $Q$ 个查询。每个查询给出一个平面上的像素 $p$。对于每个查询，输出包含像素 $p$ 的矩形的数量。

实现细节

你需要实现以下函数：

vector<long long int> count_enclosing_rectangle(vector< pair<int, int> > R1, vector< pair<int, int> > R2, vector<int> V, vector<int> I, vector<int> D, vector< pair<int, int> > P);

• 该函数只会被调用一次。
• 参数 R1 和 R2 的大小为 $N$。数组的每个元素表示初始给定的 $N$ 个矩形之一，R1[i] 和 R2[i] 分别表示第 $i+1$ 个矩形的最左下角像素和最右上角像素的坐标。如果坐标对为 $(a, b)$，则位置为 $(a, b)$。这里，矩形用 $1$ 到 $N$ 的整数表示。
• 参数 V、I、D 的大小为 $M$。数组的每个元素表示 $M$ 个矩形移动命令之一，表示矩形 I[i] 向 V[i] 方向移动距离 D[i]。
• 参数 P 的大小为 $Q$。数组的每个元素表示查询的平面上的像素 $p$ 的坐标。如果坐标对为 $(a, b)$，则位置为 $(a, b)$。
• 该函数返回一个长度为 $Q$ 的数组，表示每个查询的结果。第 $i$ $(0 \leq i \leq Q-1)$ 个值是第 $i$ 个查询的结果。

注意，提交的代码中不应包含任何输入输出操作。

样例

考虑 $N=3$, $M=3$, $Q=4$, $\mathrm{R1}=[(1,1),(3,3),(4,1)]$, $\mathrm{R2}=[(2,2),(4,4),(6,2)]$, $V=[1,6,2]$, $I=[1,2,3]$, $D=[2,2,3]$, $P=[(3,3),(4,3),(3,2),(5,3)]$ 的情况。

评测程序将调用如下函数：

count_enclosing_rectangle(R1, R2, V, I, D, P);

在这个样例中，如下图所示，$3$ 个矩形的 $3$ 次移动共生成了 $7$ 个矩形。因此，最终屏幕上有 $10$ 个矩形。像素 $(3,3)$ 包含在矩形 $1$ 生成的 $2$ 个矩形和矩形 $2$ 生成的 $2$ 个矩形中，总共包含在 $4$ 个矩形中。注意，矩形 $1$ 移动的第三个矩形和矩形 $2$ 是相同的区域，但被视为不同的矩形。

count_enclosing_rectangle 函数应返回数组 $[4, 5, 3, 2]$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 2.5\cdot 10^5$
• $0 \leq M \leq 2.5\cdot 10^5$
• $1 \leq Q \leq 2.5\cdot 10^5$
• $1 \leq \mathrm{R1}[i].\text{first} \leq \mathrm{R2}[i].\text{first} \leq 2.5\cdot 10^5$
• $1 \leq \mathrm{R1}[i].\text{second} \leq \mathrm{R2}[i].\text{second} \leq 2.5\cdot 10^5$
• $0 \leq \mathrm{V}[i] \leq 7$
• $1 \leq \mathrm{I}[i] \leq N$
• $1 \leq \mathrm{D}[i] \leq 2.5\cdot 10^5$
• 屏幕的坐标值在 $1$ 到 $2.5\cdot 10^5$ 之间。任意矩形包含的所有像素的坐标值始终在此范围内。移动后也满足此条件。查询给出的像素也满足此条件。
• 矩形的移动方向 $\mathrm{V}[i]$ 的值为 $0$（东）、$1$（东北）、$2$（北）、$3$（西北）、$4$（西）、$5$（西南）、$6$（南）、$7$（东南）。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	8	$N \leq 100$, $M=0$
2		$M=0$
3	11	$M \leq 100$
4	13	$\mathrm{V}[i] \in \{0,2,4,6\}$ $(0 \leq i \leq M-1)$，即矩形只向上下左右移动
5	12	$\mathrm{R1}[i]=\mathrm{R2}[i]$ $(0 \leq i \leq N-1)$
6	48	无附加限制

示例评测程序

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$ $M$ $Q$
• 第 $1+i$ $(1 \leq i \leq N)$ 行：$\mathrm{R1}[i-1].\text{first}$ $\mathrm{R1}[i-1].\text{second}$ $\mathrm{R2}[i-1].\text{first}$ $\mathrm{R2}[i-1].\text{second}$
• 第 $1+N+i$ $(1 \leq i \leq M)$ 行：$\mathrm{V}[i-1]$ $\mathrm{I}[i-1]$ $\mathrm{D}[i-1]$
• 第 $1+N+M+i$ $(1 \leq i \leq Q)$ 行：$\mathrm{P}[i-1].\text{first}$ $\mathrm{P}[i-1].\text{second}$

示例评测程序的输出格式如下：

• 第 $i$ $(1 \leq i \leq Q)$ 行：函数 count_enclosing_rectangle 返回的数组的第 $i$ 个元素。

示例评测程序可能与实际评测程序不同。

---