时间限制： 7.0 秒

空间限制： 1024 MB

题目描述

给定一个二维平面上的 $n$ 个点，每个点有一个整数权值。你需要做 $q$ 次矩形区域查询，每次返回矩形区域内的最小权值和最大权值。你需要强制在线完成全部查询。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 rangequery.h。

给定点的接口定义为：

struct Point { int x, y, v; };

代表一个坐标位于 $(x,y)$ 的点，权值为 $v$。

给定查询矩形的接口定义为：

struct Query { int X1, X2, Y1, Y2; };

查询的矩形区域的四边分别与 $x$ 或 $y$ 轴平行，$(X_1, Y_1)$ 和 $(X_2, Y_2)$ 描述其一条对角线。恰好位于矩形边界的点，也视作落在其中。

你需要实现以下函数：

void init(const std::vector<Point>& pts);

这是初始化函数。交互库首先会调用这个函数，你可以在此对你的程序进行初始化。

其中 pts 代表二维平面当中的各点情况。

std::pair<int, int> query(const Query& q);

这是查询函数。在初始化完成后，交互库会调用这个函数 $q$ 次，每一次你都需要进行相应地查询并报告结果。

对于每次查询，你需要报告区域内的最小权值、最大权值，分别存入返回的 std::pair<int, int> 的 first、second 当中。如果在区域内没有点，请返回 -1 -1。

以下我们给出一个代码提交实例（返回权值均为随机数，仅作为可以通过编译的示例，不保证能得分）。

#include <stdlib.h>
#include "rangequery.h"
// nothing to init
void init(const std::vector<Point>& pts) {}
// retrurn random number
std::pair<int, int> query(const Query& q) { return {(int)rand(), (int)rand()}; }

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 rangequery.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

交互库将从标准输入读入如下格式的输入数据：

1. 第一行一个整数 $n$
2. 接下来 $n$ 行，每行三个整数 $x_i,y_i,v_i\ (0\le i<n)$。
3. 接下来 $q$ 行，每行四个整数 $X_1,X_2,Y_1,Y_2$，为每次查询的矩形区域。但是 $q$ 在白盒交互库中不可见，以文件末尾符 EOF 作为查询结束。

对于每次查询，白盒交互库将输出两个整数到标准输出，分别为矩形区域的最小值和最大值。

4
0 0 100
1 2 200
1 2 3000
3 3 4000
0 0 0 0
-1 -1 -1 -1
0 2 0 2
1 3 2 3

100 100
-1 -1
100 3000
200 4000

子任务

对于所有数据，保证：

• $n,q\le 6\times 10^5$
• $-2^{31}\le x_i,y_i<2^{31}$
• $0\le v_i<2^{31}$
• $-2^{31}\le X_1\le X_2<2^{31}$
• $-2^{31}\le Y_1\le Y_2<2^{31}$

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

本题实现区域树/kd-树可以获得部分分数，可以视为大致掌握了搜索树应用一章中，高维查询部分的关键内容。

你需要针对区域树实现分散层叠（Fractional Cascading）优化才能获得全部分数，可视为掌握搜索树应用一章中，区域树的全部内容。

如果通过仔细分析发现复杂度依旧无法达到理想状态，可以参考基于状态压缩的线性 RMQ 算法进行复杂度的优化设计，此处给出其中一种常数较优实现方式作为参考。

来源

DSA OJ 编程作业，数据范围有所改动。