Problem 1. Paint by Rectangles

USACO 2022 February Contest, Platinum

在

Bessie 的上一幅画作

备受好评之后，她获得了设计画作的工作。她通过在平面中选择 $1\le N\le 10^5$ 个四边与坐标轴平行的矩形来设计画作，其中没有两条边共线。这些矩形的边界确定了这幅画作的着色区域的边界。

作为一名先锋派艺术家，Bessie 认为这幅画作应该要像一头荷斯坦奶牛。更具体地说，这些矩形形成的每个区域都被着色为黑色或白色，没有两个相邻区域的颜色相同，并且所有矩形之外的区域被着色为白色。

选定矩形后，Bessie 希望您根据参数 $T$ 输出以下两项之一：

• 如果 $T=1$，输出区域的总数。
• 如果 $T=2$，输出白色区域的数量和黑色区域的数量。

注意：本题的时间限制为 4 秒，通常限制的两倍。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $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_1, y_1)$ 和 $(x_2, y_2)$ 分别是矩形的左下角和右上角。

输入保证所有的 $x_i$ 构成 $1\ldots 2N$ 的一个排列，所有的 $y_i$ 构成 $1\ldots 2N$ 的一个排列。

输出格式（输出至终端 / 标准输出）：

如果 $T=1$，输出一个整数，否则输出两个空格分隔的整数，表示所求的答案。

输入样例：

2 1
1 1 3 3
2 2 4 4

输出样例：

4

有两个白色区域和两个黑色区域，总共四个区域。所有矩形的边界是连通的，所以这个测试点满足子任务 3 的性质。

输入样例：

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

输出样例：

4 5

右上方的矩形的边界与其他矩形的边界不连通，所以这个测试点不满足子任务 4 的性质。

测试点性质： 测试点 3-4 满足 $N\le 10^3$。测试点 5-7 中，没有两个矩形的边界相交。测试点 8-10 中，$T=1$ 并且所有矩形的边界连通。测试点 11-13 中，$T=2$ 并且所有矩形的边界连通。测试点 14-18 中，$T=1$。测试点 19-23 中，$T=2$。

供题：Andi Qu