矩形区域计数

题目描述

小 $z$ 有一个无限大的网格图。 现在他想在网格图上覆盖一些矩形，第 $i$ 个矩形的左上角的网格的坐标为 $x 1_i, y 1_i$ ，右下角的网格的坐标为 $x 2_i, y 2_i$ 。 现在小 $z$ 想知道网格图上未被覆盖的网格构成多少个连通块，如果两个未被覆盖的网格有公共边，则它们在一个连通块内。 特别地，最外面一圈的无限延伸的网格也算是一个连通块。例如：如果没有覆盖矩形，答案是 1 。

输入格式

• 第一行一个整数 $n\left(1 \leq n \leq 10^5\right)$ 。 接下来第 2 到 $n+1$ 行，第 $i+1$ 行有 4 个用空格隔开的数，分别代表 $x 1_i, x 2_i, y 1_i, y 2_i, 1 \leq x 1_i \leq x 2_i \leq 10^9, 1 \leq y 1_i \leq y 2_i \leq 10^9 。$

输出格式

输出一个整数，表示连通区域个数。

样例输入1

1
1 1 1 1

样例输出1

1

样例输入2

4
1 1 1 10
1 10 1 1
1 10 10 10
10 10 1 10

样例输出2

2

样例输入3

6
1 1 1 10
1 10 1 1
1 10 10 10
10 10 1 10
5 5 1 10
1 10 5 5

样例输出3

5

限制

第一档 $1 \le n \le 100$ ,$1 \leq x1_i \leq x2_i \leq 1000$, $1\leq y1_i \leq y2_i \leq 1000$

第二档 $1 \leq n \leq 10000$ ,$1 \leq x1_i \leq x2_i \leq 3$, $1\leq y1_i \leq y2_i \leq 100000$

第三档 $1 \leq n \leq 10000$ ,$1 \leq x1_i \leq x2_i \leq 10$, $1\leq y1_i \leq y2_i \leq 100000$

第四档 $1 \leq n \leq 10000$ ,$1 \leq x1_i \leq x2_i \leq 20$, $1\leq y1_i \leq y2_i \leq 100000000$

第五档 $1 \leq n \leq 10000$ ,$1 \leq x1_i \leq x2_i \leq 1000000000$, $1\leq y1_i \leq y2_i \leq 1000000000$ 保证$x1_i+1==x2_i$

第六档 $1 \leq n \leq 100000$ ,$1 \leq x1_i \leq x2_i \leq 1000000000$, $1\leq y1_i \leq y2_i \leq 1000000000$

一到五档各15分，最后一档25分。