题目描述

译自 ROI 2024 Day1 T4. Рамазан и капуста

拉马赞决定从事种植卷心菜的生意。

种植卷心菜的田地是一个无限的方格场地。每个格子里可以种植一个卷心菜。

拉马赞只种植了部分田地。他计划使用几个矩形区域，这些区域可能会相交。如果一个格子位于至少一个矩形区域内，则该格子属于种植区。

具体来说，拉马赞选择了 $n$ 个矩形区域 $(x_i^{L}, y_i^{L}, x_i^{R}, y_i^{R})\ (x_i^{L} \leq x_i^{R}, y_i^{L} \leq y_i^{R}, 1 \leq i \leq n)$。如果存在至少一个选定的矩形 $i\ (1 \leq i \leq n)$，使得 $x_i^{L} \leq x \leq x_i^{R}$ 且 $y_i^{L} \leq y \leq y_i^{R}$，则格子 $(x, y)$ 中就有卷心菜。

过去，拉马赞是一名程序员（并且是一名获奖者），因此他决定使用带有人工智能的机器人定期处理种植区。一个机器人可以服务任意一个水平区域的格子 $(x_1^{robot}, x_2^{robot}, y^{robot})$，即所有满足 $x_1^{robot} \leq x \leq x_2^{robot}$ 且 $y = y^{robot}$ 的格子 $(x, y)$。

重要的是，机器人只能在种植区域内行驶。他意识到，为了最小化机器人的数量，重要的是使用无法扩展的水平区域。满足下列条件时，拉马赞将在区域 $(x_1^{robot}, x_2^{robot}, y^{robot})$ 上使用机器人：

• 所有满足 $x_1^{robot} \leq x \leq x_2^{robot}$ 且 $y = y^{robot}$ 的格子都属于种植区；
• 格子 $(x_1^{robot} - 1, y^{robot})$ 不属于种植区；
• 格子 $(x_2^{robot} + 1, y^{robot})$ 不属于种植区。

你的任务是收集将在种植园工作的机器人的重要统计数据。如果在某一行 $y$ 中存在一个机器人恰好在区域 $(x_1, x_2, y)$ 上工作，我们说对 $(x_1, x_2)$ 进行了服务。

• 找出所有在某一行中被服务的对 $(x_1, x_2)$。
• 对于每一对 $(x_1, x_2)$，找出它被服务的行数。
• 对于每一对 $(x_1, x_2)$，找出它连续被服务的最大行数。换句话说，找出最大的数 $k$，使得存在一个连续的行区间 $[y_1, y_2]\ (y_2 - y_1 + 1 = k)$，对于任何行 $y_1 \leq y \leq y_2$，对 $(x_1, x_2)$ 都进行了服务。

输入格式

输入包含多组数据。第一行包含一个整数 $t\ (1 \leq t \leq 2\cdot 10^5)$，表示测试数据的组数。

每组输入数据的第一行给出了一个整数 $n\ (1 \leq n \leq 2\cdot 10^5)$，表示选定的矩形区域的数量。

接下来的 $n$ 行，每行给出了四个整数 $x_i^{L}, y_i^{L}, x_i^{R}, y_i^{R}\ (1 \leq x_i^{L} \leq x_i^{R} \leq 10^9, 1 \leq y_i^{L} \leq y_i^{R} \leq 10^9)$，表示选定的矩形区域。

令 $N$ 表示一个测试中所有输入数据组的 $n$ 之和。保证 $N \leq 2\cdot 10^5$。

输出格式

对于每组输入数据，首先输出一个整数 $p\ (p \geq 1$)，表示在某一行中被服务的对 $(x_1, x_2)$ 的数量。

在接下来的 $p$ 行中，每行输出四个整数 $x_1, x_2, cnt, k\ (1 \leq x_1 \leq x_2 \leq 10^9, 0 \leq cnt, k \leq 10^9)$。数字 $cnt$ 应等于对 $(x_1, x_2)$ 进行服务的行数。数字 $k$ 应等于对 $(x_1, x_2)$ 连续进行服务的最大行数。

所有对 $(x_1, x_2)$ 必须是不同的。每一对在某一行中被服务的对，必须恰好输出一次。你可以以任意顺序输出对。

4
2
2 2 3 3
3 3 4 4
2
2 1 2 3
1 2 3 2
4
2 2 4 5
3 4 9 7
2 9 9 10
7 1 9 7
7
2 1 2 9
5 1 6 8
4 5 7 6
1 8 4 10
1 6 3 6
1 2 7 3
4 1 7 1

3
2 3 1 1
2 4 1 1
3 4 1 1
2
1 3 1 1
2 2 2 1
4
2 4 2 2
2 9 4 2
3 9 2 2
7 9 3 3
6
1 4 2 2
1 6 1 1
1 7 3 2
2 2 4 2
4 7 2 1
5 6 2 1

在第一组输入数据中，将使用区域 $(2, 3, 2),(2, 4, 3),(3, 4, 4)$ 上的机器人。因此，对 $(2, 3),(2, 4),(3, 4)$ 在某一行中被服务，每一对都恰好在一行中被服务。

在第二组输入数据中，将使用区域 $(2, 2, 1),(2, 4, 2),(2, 2, 3)$ 上的机器人。因此，对 $(2, 2),(2, 4)$ 在某一行中被服务。对 $(2, 2)$ 在行 $1, 3$ 中被服务，对 $(2, 4)$ 在行 $2$ 中被服务。

数据范围与提示

对于所有输入数据组，用 $w$ 表示田地的宽度，即 $w = \max\limits_{i=1}^{n} x_i^{R}$，用 $h$ 表示田地的高度，即 $h = \max\limits_{i=1}^{n} y_i^{R}$。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$n, N$ 的限制	$w, h$ 的限制	附加限制	子任务依赖
$1$	$4$	$n = 1$
$2$	$8$		$h = 1$
$3$	$8$	$n \leq 30$, $N \leq 3000$	$w$, $h \leq 10$	$t \leq 100$	$0$
$4$	$4$		$w$, $h \leq 5000$, $\sum wh \leq 25 \cdot 10^6$		$0, 3$
$5$	$8$	$N \leq 3000$
$6$	$4$	$N \leq 10^4$			$0, 3, 5$
$7$	$8$			所有 $[x_i^{L}, x_i^{R}]$ 相交	$1$
$8$	$8$			$y_i^{L} = 1$	$2$
$9$	$8$			矩形不相交	$1$
$10$	$8$			$\forall y\in [y_i^{L}, y_i^{R}] \cap [y_j^{L}, y_j^{R}]\ (1 \leq i, j \leq n)$ 都有 $[x_i^{L}, x_i^{R}] \nsubseteq [x_j^{L}, x_j^{R}]$	$1, 9$
$11$	$8$			所有区间 $[x_i^{L}, x_i^{R}+1]$ 要么嵌套，要么不相交	$1$
$12$	$8$	$N \leq 5\cdot 10^4$			$0, 3, 5 - 6$
$13$	$8$	$N \leq 10^5$			$0, 3, 5 - 6, 12$
$14$	$8$	$N \leq 2\cdot 10^5$			$0, 1 - 13$

• 如果你的程序错误地找到了在某一行中被服务的对 $(x_1, x_2)$ 的集合，你的程序将得到「Wrong Answer」的结果。
• 如果在子任务的所有测试数据中，你的程序：
  • 正确找到了集合，但不是所有的 $cnt$ 都正确，它将获得子任务的 $50\%$ 分数。
  • 正确找到了集合和所有的 $cnt$，但不是所有的 $k$ 都正确，它将获得子任务的 $75\%$ 分数。
  • 正确找到了集合，所有的 $cnt$ 和所有的 $k$，它将获得子任务的 $100\%$ 分数。

请注意，为了获得子任务的部分分数，仍然需要为每对 $(x_1, x_2)$ 输出一些 $cnt$ 和 $k$ 的值，但不一定是正确的。