Paint by Rectangles

题目描述

在她之前的艺术作品获得评论界一致好评后，Bessie 得到了一份设计绘画布景的工作。她通过在平面上选择 $1\le N\le 10^5$ 个与坐标轴对齐的矩形来设计这些画作，并且任意两条边都不共线。这些矩形的边界定义了画作中各个着色区域的边界。

作为一位前卫艺术家，Bessie 决定让画作看起来像一头荷斯坦奶牛。更具体地说，由这些矩形形成的每个区域都被染成黑色或白色，任意两个相邻区域颜色不同，并且所有矩形之外的区域被染成白色。

在选择完矩形后，Bessie 希望你根据参数 $T$ 输出以下两种结果之一： 如果 $T=1$，输出区域总数。 如果 $T=2$，输出白色区域数量，然后输出黑色区域数量。

注意：本题时间限制为 4s，是默认时间限制的两倍。

输入格式

第一行包含 $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

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 的条件。

评分（SCORING）： 测试点 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

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum