#P18395. Pixel Art
Pixel Art
Pixel Art
DreamGrid 正在一个 行 列的网格上创作像素画。初始所有格子都是白色,他只能画水平或竖直的线段。
记第 行、第 列的格子为 :
- 水平线段 ()包含所有满足 且 的格子。
- 竖直线段 ()包含所有满足 且 的格子。
- 画一条线段会将这条线段包含的所有格子涂黑。
经过一段时间,他画出了 条互不相交的线段。他还希望研究这幅作品的数学性质。
令 表示原网格的前 行构成的子网格, 表示 中黑色格子的数量, 表示 中黑色连通块的数量。请计算所有 对应的 。
两个黑格属于同一个连通块,当且仅当存在一条完全由黑格组成的路径,从一个格子到达另一个格子,且路径上连续两个格子共享一条边。仅在角上接触不算连通。
输入格式
第一行包含整数 ,表示测试用例数量。
对于每个测试用例:
- 第一行包含三个整数 ()。
- 接下来 行,每行包含四个整数 ,表示一条线段。保证 ,,且 或 。
若 ,表示第 行从第 列到第 列的水平线段。若 ,表示第 列从第 行到第 行的竖直线段。两个等式可能同时成立,此时线段仅包含一个格子。
保证同一测试用例中的任意两条线段不会包含同一个格子,共享端点格子也算相交。线段之间允许相邻。
保证所有测试用例的 之和不超过 , 之和不超过 ;不保证 的总和有上界。原题未另给 上限,由 可知 。
输出格式
对于每个测试用例,输出 行。第 行输出 和 ,用一个空格分隔。
样例
3
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3
2 1
5 2
3 1
6 1
3 1
4 1
6 2
样例说明
下面的原图展示了三个测试用例,格子中的数字表示所属线段在该测试用例中的编号。

第三个测试用例的第一行有 3 个黑格、1 个连通块;前两行有 4 个黑格、1 个连通块;全部三行有 6 个黑格、2 个连通块。因此对应输出为 3 1、4 1、6 2。