A6127. 「USACO 2022.2 Platinum」Paint by Rectangles
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目译自 [USACO 2022 February Contest, Platinum](http://usaco.org/index.php?page=feb22results) Problem 1. [Paint by Rectangles](http://usaco.org/index.php?page=viewproblem2&cpid=1212)**
在平面上画 $N$（$1\le N\le 10^5$）个矩形，这些矩形将平面分割成若干个区域，可以将这些区域进行黑白染色，规定其中面积无穷大的区域为白色。
给定参数 $T$，若 $T=1$，输出总共的区域数，否则先输出白色区域的数量，再输出黑色区域的数量。
在平面上画 $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$ 的排列。
接下来 $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
输出 #1
4
输入 #2
5 2 1 5 3 6 5 4 7 9 4 1 8 3 9 8 10 10 2 2 6 7
输出 #2
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$。
- 测试点 $5\sim 7$ 满足任何两个矩形的边界不相交。
- 测试点 $8\sim 10$ 满足 $T=1$，且所有矩形的边界连通。
- 测试点 $11\sim 13$ 满足 $T=2$，且所有矩形的边界连通。
- 测试点 $14\sim 18$ 满足 $T=1$。
- 测试点 $19\sim 23$ 满足 $T=2$。