AdditionalFile4282.zip

#4282. 「KTSC 2021 R1」卡顿

标签: 传统 | 时间限制: 8000 ms | 内存限制: 1024 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "lag.h"。

题目描述

题目译自 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）。

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

执行完 $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$ 之间。任意矩形包含的所有像素的坐标值始终在此范围内。移动后也满足此条件。查询给出的像素也满足此条件。
• 矩形的移动方向 $V[i]$ 的值为 $0$（东）、$1$（东北）、$2$（北）、$3$（西北）、$4$（西）、$5$（西南）、$6$（南）、$7$（东南）。

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

示例评测程序

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

• 第 $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$ 个元素。

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