8851: [yosupo] Data Structure - Area of Union of Rectangles
[Creator : ]
Description
Given $N$ rectangles : the $i$-th rectangle is represented by $\lbrace (x,y):l_i \leq x \leq r_i,d_i \leq y \leq u_i \rbrace$.
Output the area of the union set of these rectangles.
Output the area of the union set of these rectangles.
Input
$N$
$l_0$ $d_0$ $r_0$ $u_0$
$l_1$ $d_1$ $r_1$ $u_1$
$\vdots$
$l_{N-1}$ $d_{N-1}$ $r_{N-1}$ $u_{N-1}$
$l_0$ $d_0$ $r_0$ $u_0$
$l_1$ $d_1$ $r_1$ $u_1$
$\vdots$
$l_{N-1}$ $d_{N-1}$ $r_{N-1}$ $u_{N-1}$
Constraints
- $1 \le N \le 500,000$
- $0 \le l_i < r_i \le 10^9$
- $0 \le d_i < u_i \le 10^9$
- $0 \le l_i < r_i \le 10^9$
- $0 \le d_i < u_i \le 10^9$
Sample 1 Input
3
1 1 2 5
2 1 5 2
1 2 2 5
Sample 1 Output
7