P6976: 矩形绘画
传统题
4.000s
时间限制
256MB
内存限制
4 提交
1 解决
【题目描述】
【题目描述】在 Bessie 的上一幅画作备受好评之后，她获得了设计画作的工作。她通过在平面中选择 1≤N≤10^5 个四边与坐标轴平行的矩形来设计画作，其中没有两条边共线。这些矩形的边界确定了这幅画作的着色区域的边界。
作为一名先锋派艺术家，Bessie 认为这幅画作应该要像一头荷斯坦奶牛。更具体地说，这些矩形形成的每个区域都被着色为黑色或白色，没有两个相邻区域的颜色相同，并且所有矩形之外的区域被着色为白色。
选定矩形后，Bessie 希望您根据参数 T 输出以下两项之一：
如果 T=1，输出区域的总数。
如果 T=2，输出白色区域的数量和黑色区域的数量。
**注意：本题的时间限制为 4 秒，通常限制的两倍。**
【输入格式】（从终端 / 标准输入读入）：
输入的第一行包含 N 和 T。
以下 N 行，每行以 (x1,y1),(x2,y2) 的格式表示一个矩形，其中 1≤x1<x2≤2N 以及 1≤y1<y2≤2N。(x1,y1) 和 (x2,y2) 分别是矩形的左下角和右上角。
输入保证所有的 xi 构成1…2N 的一个排列，所有的 yi 构成 1…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≤10^3。
测试点 5-7 中，没有两个矩形的边界相交。
测试点 8-10 中，T=1 并且所有矩形的边界连通。
测试点 11-13 中，T=2 并且所有矩形的边界连通。
测试点 14-18 中，T=1。
测试点 19-23 中，T=2。