화성 지도

2051년, 야심차게 발사한 화성 탐사선 성화가 탐사한 지역의 화성 지도를 N장 보내왔다.

탐사선의 성공에 고무된 우주국은 화성 전체 지도를 완성하겠다는 야심찬 계획을 발표했다.

전체 지도를 만들기에 앞서, 지금까지 탐사선이 보낸 지도를 모두 겹쳐서 하나로 합쳤다. 이렇게 합친 지도가 실제로 덮고 있는 영역의 넓이는 얼마일까?

탐사선이 보낸 각 지도는 항상 변이 좌표축에 평행한 직사각형이며, 서로 겹칠 수 있다.

첫째 줄에 탐사선이 보낸 지도의 수 N (1 ≤ N ≤ 10,000)이 주어진다.

다음 N개의 줄에는 각 지도의 정보가 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000)로 주어진다. (x1, y1)은 직사각형의 왼쪽 아래 꼭짓점, (x2, y2)는 오른쪽 위 꼭짓점의 좌표이다. 모든 직사각형의 변은 x축 또는 y축에 평행하다.

첫째 줄에, 탐사선이 지금까지 보낸 모든 지도를 겹쳐 합쳤을 때 덮인 영역 전체의 넓이를 출력한다.

여러 직사각형의 합집합의 넓이를 구하는 문제이다. x좌표를 기준으로 평면을 훑는 스위핑(sweeping) 기법과 y좌표 좌표압축 + 세그먼트 트리를 사용하면 O(N log N)에 해결할 수 있다.