注意事项

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

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

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

题目描述

题目译自 2025년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4 「안전 지대」

由于僵尸病毒的肆虐，地球已经沦陷，仅剩 $N$ 个军事基地幸存下来。地球被视为一个坐标空间上的矩形区域，范围为 $-10^{9} \leq x \leq 10^{9}, -10^{9} \leq y \leq 10^{9}$。每个军事基地负责管理一块矩形的安全区域。具体来说，对于 $0 \leq i \leq N-1$，第 $i$ 个军事基地管理的区域是满足 $A[i] \leq x \leq C[i], B[i] \leq y \leq D[i]$ 的矩形，包括边界和内部。

如果两个军事基地的安全区域有至少一个公共点，它们就被认为是连接的。如果存在 $0 \leq i, j, k \leq N-1$，且 $i \neq j, j \neq k, k \neq i$，使得 $i$ 号基地与 $j$ 号基地连接，$j$ 号基地又与 $k$ 号基地连接，那么 $i$ 号基地和 $k$ 号基地也算连接。一个军事基地的集合，若其中所有基地互相连接，且与集合外的任何基地都不连接，这样的集合被称为一个联盟。

你是火星基地的一名官员，需要向地球派遣补给线。为了高效配送，你需要根据地球上各军事基地的安全区域信息，编写一个函数来识别所有的联盟。

实现细节

你需要实现以下函数：

vector<int> find_union(int N, vector<int> A, vector<int> B, vector<int> C, vector<int> D)

• N：军事基地的数量。
• A, B, C, D：长度为 $N$ 的数组。对于所有 $0 \leq i \leq N-1$，满足 $A[i] \leq C[i], B[i] \leq D[i]$。第 $i$ 个军事基地管理的区域为 $A[i] \leq x \leq C[i], B[i] \leq y \leq D[i]$。
• 设 $M$ 为联盟的总数。
• 函数需返回一个长度为 $N$ 的数组 $U$，其中 $U[i]$ 表示第 $i$ 个军事基地所属联盟的编号。
• 必须满足 $0 \leq U[i] \leq M-1$。
• 对于所有 $0 \leq i, j \leq N-1, i \neq j$，若 $U[i] = U[j]$，则 $i$ 号基地与 $j$ 号基地必须连接。
• 对于所有 $0 \leq i, j \leq N-1, i \neq j$，若 $U[i] \neq U[j]$，则 $i$ 号基地与 $j$ 号基地不得连接。

你提交的代码中不得包含任何输入输出函数。

样例 1

假设 $N=3$，$A=[0,1,2]$，$B=[0,1,-1]$，$C=[1,2,4]$，$D=[1,2,0]$。评测程序调用：

find_union(3, {0, 1, 2}, {0, 1, -1}, {1, 2, 4}, {1, 2, 0})

各军事基地的安全区域在坐标平面上的分布如下：

$1$ 号基地和 $2$ 号基地共享点 $(1,1)$，因此它们连接。而 $0$ 号基地与任何其他基地都不相连。所以总共有 $2$ 个联盟：一个包含 $1$ 号和 $2$ 号基地，另一个只有 $0$ 号基地。

函数可以返回 $[0,0,1]$，表示 $0$ 号基地在联盟 $0$，$1$ 号和 $2$ 号基地在联盟 $1$。另一种可能的返回值是 $[1,1,0]$。

样例 2

假设 $N=2$，$A=[0,2]$，$B=[1,0]$，$C=[3,4]$，$D=[3,2]$。评测程序调用：

find_union(2, {0, 2}, {1, 0}, {3, 4}, {3, 2})

函数应返回 $[0,0]$。

数据范围与提示

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

• $1 \leq N \leq 500000$
• $-10^{9} \leq A[i], B[i], C[i], D[i] \leq 10^{9}$（对于所有 $0 \leq i \leq N-1$）
• $A[i] \leq C[i], B[i] \leq D[i]$

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

子任务	分值	附加限制
$1$	$3$	对于所有 $0 \leq i \leq N-1$，$A[i] \leq i \leq C[i], B[i] \leq 0 \leq D[i]$（）
$2$	$4$	对于所有 $0 \leq i \leq N-1$，$B[i] \leq 0 \leq D[i]$
$3$	$7$	$N \leq 5000$
$4$	$21$	$A[i] = C[i]$ 或 $B[i] = D[i]$
$5$	$26$	$N \leq 100000$
$6$	$39$	无附加限制

示例评测程序

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

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$A[i]\ B[i]\ C[i]\ D[i]$

输出格式如下：

• 第 $1$ 行：$U[0]\ U[1]\ \cdots\ U[N-1]$

请注意，示例评测程序可能与实际评测程序有所不同。