#PU1212. USACO 2022 February Contest, Platinum — Problem 1. Paint by Rectangles

    ID: 1337 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb22来源:usaco.orgscoring:equal_test_cases并查集线段树

USACO 2022 February Contest, Platinum — Problem 1. Paint by Rectangles

USACO 2022 February Contest, Platinum — Problem 1. Paint by Rectangles

题目描述

After her previous artwork was met with critical acclaim, Bessie was offered a job designing painting sets. She designs these paintings by choosing 1≤N≤1051\le N\le 10^5 axis-aligned rectangles in the plane such that no two edges are collinear. The boundaries of these rectangles define the boundaries of the painting's colored regions. Still being an avant-garde artist, Bessie decides that the painting should resemble a Holstein cow. More specifically, each region formed by the rectangles is colored either black or white, no two adjacent regions have the same color, and the region outside of all the rectangles is colored white. After choosing the rectangles, Bessie would like you to output one of two things based on a parameter TT: If T=1T=1, output the total number of regions. If T=2T=2, output the number of white regions followed by the number of black regions. Note: the time limit for this problem is 4s, twice the default.

输入格式

The first line contains NN and TT. The next NN lines each contain the description of a rectangle in the form (x1,y1),(x2,y2)(x_1,y_1), (x_2,y_2) where 1≤x1<x2≤2N1\le x_1<x_2\le 2N and 1≤y1<y2≤2N1\le y_1<y_2\le 2N. (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) are the bottom left and top right corners of the rectangle respectively. It is guaranteed that all the xix_i form a permutation of 1…2N1\ldots 2N, and the same holds for all the yiy_i.

输出格式

A single integer if T=1T=1, otherwise two separated by spaces.

数据范围

Test cases 3-4 satisfy N≤103N\le 10^3. In test cases 5-7, no two rectangle boundaries intersect. In test cases 8-10, T=1T=1 and the boundaries of all rectangles are connected. In test cases 11-13, T=2T=2 and the boundaries of all rectangles are connected. In test cases 14-18, T=1T=1. In test cases 19-23, T=2T=2. Problem credits: Andi Qu

样例

样例 1

2 1
1 1 3 3
2 2 4 4
4
There are two white regions and two black regions, for a total of four regions.
The boundaries of all rectangles are connected, so this input would satisfy the
conditions of subtask 3.

样例 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
The boundary of the rectangle in the upper-right is not connected to the rest of
the boundaries, so this input would not satisfy the conditions of subtask 4.