时间限制： 4.0 秒

空间限制： 256 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::vector<std::pair<int, int>> query(const std::vector<Query>& queries);

这是查询函数。在初始化完成后，交互库会将全部的 $q$ 次查询统一通过调用一次 query，你需要按照查询数组中的排列方式顺次存储你的答案。

对于每次查询，你需要报告区域内的最小权值、最大权值，分别存入返回的 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::vector<std::pair<int, int>> query(const std::vector<Query>& queries) 
{ 
    int q = (int)queries.size();
    std::vector<std::pair<int, int>> ret(q);
    for (int i = 0; i < q; ++i) ret[i] = {(int)rand(), (int)rand()};
    return ret;
}

白盒交互库实例

具体请见附加文件区的 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,q$
2. 接下来 $n$ 行，每行三个整数 $x_i,y_i,v_i\ (0\le i<n)$。
3. 接下来 $q$ 行，每行四个整数 $X_1,X_2,Y_1,Y_2$，为每次查询的矩形区域。

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

4 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}$

提示

在高维区域查询 1 的分散层叠优化区域树的基础上，可以发现外层线段树的结构当中，每一层的点个数与查询个数都是线性的，因此可以离线逐层处理。空间复杂度的优化会带来时间常数的大幅度优化。

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

来源

DSA OJ 编程作业，改编。