该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3667.zip](file://AdditionalFile3667.zip?type=additional_file)

#3667. 「USACO 2022.2 Platinum」Paint by Rectangles

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

题目译自 USACO 2022 February Contest, Platinum Problem 1. Paint by Rectangles

在平面上画 $N$（$1\le N\le 10^5$）个矩形，这些矩形将平面分割成若干个区域，可以将这些区域进行黑白染色，规定其中面积无穷大的区域为白色。

给定参数 $T$，若 $T=1$，输出总共的区域数，否则先输出白色区域的数量，再输出黑色区域的数量。

输入格式

第一行输入两个正整数 $N$ 和 $T$。

接下来 $N$ 行输入矩形的两角 $(x_1,y_1)$ 和 $(x_2, y_2)$，保证 $1\le x_1<x_2\le 2N$，$1\le y_1<y_2\le 2N$，且所有的 $x_i$、所有的 $y_i$ 各自构成 $1,\dots,2N$ 的排列。

输出格式

如果 $T=1$ 输出一个整数，否则输出两个整数。

样例 1

输入

2 1
1 1 3 3
2 2 4 4

输出

4

样例 2

输入

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

输出

4 5

数据范围与提示

• 测试点 $3,4$ 满足 $N\le 10^3$。
• 测试点 $5\sim 7$ 满足任何两个矩形的边界不相交。
• 测试点 $8\sim 10$ 满足 $T=1$，且所有矩形的边界连通。
• 测试点 $11\sim 13$ 满足 $T=2$，且所有矩形的边界连通。
• 测试点 $14\sim 18$ 满足 $T=1$。
• 测试点 $19\sim 23$ 满足 $T=2$。