행사장 대여 (Large)

면접 대비

시간 제한5초메모리 제한256 MB

요약

최대 3000개의 축에 평행한 직사각형이 주어질 때, 겹치는 부분을 한 번만 세어 합집합의 넓이를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 세그먼트 트리, 누적 합
정답자: 아직 제출이 없습니다

문제

상현이는 국방부 퀘스트를 수행하기 전에 이별 파티를 열려고 한다. 파티를 치를 행사장을 빌리는 것이 첫 단계다.

대여 업체 직원이 모두 전직 프로그래머라 대여 방식이 독특하다. 상현이가 빌릴 장소를 정하면 업체는 그 장소를 빈틈없이 덮는 직사각형 $N$ 개를 만든다. 그다음 직사각형의 개수 $N$ 과 각 직사각형의 좌측 하단 좌표, 우측 상단 좌표를 알려 준다. $N$ 개의 직사각형은 일부가 겹치거나 전체가 겹칠 수도 있다. 모든 직사각형의 변은 좌표축과 평행하다.

상현이가 빌린 행사장의 넓이, 즉 직사각형 $N$ 개가 덮는 영역의 넓이를 구하는 프로그램을 작성하라.

입력

첫째 줄에 직사각형의 개수 $N$ 이 주어진다. ( $2 \le N \le 3000$ )

이어지는 $N$ 개의 줄에 네 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 순서대로 주어진다. ( $-50000 \le x_1 < x_2 \le 50000$ , $-50000 \le y_1 < y_2 \le 50000$ ) 이는 직사각형의 좌측 하단 좌표가 $(x_1, y_1)$ , 우측 상단 좌표가 $(x_2, y_2)$ 라는 뜻이다.

출력

첫째 줄에 상현이가 빌린 행사장의 넓이를 출력한다. 겹치는 부분은 한 번만 센다. 넓이는 최대 $10^{10}$ 이라 32비트 정수 범위를 넘는다.

예제7

예제 1
입력
```
3
4 2 6 3
4 0 5 1
0 0 7 8
```
예상 출력
```
56
```
예제 2
입력
```
2
0 0 2 2
5 5 7 7
```
예상 출력
```
8
```
예제 3
입력
```
2
-3 -3 3 3
-3 -3 3 3
```
예상 출력
```
36
```
예제 4
입력
```
2
0 0 2 2
2 0 4 2
```
예상 출력
```
8
```

예제 5

입력

2
-50000 -50000 50000 50000
-1 -1 1 1

예상 출력

10000000000

예제 6
입력
```
2
-4 -6 1 -1
-2 -3 5 2
```
예상 출력
```
54
```
예제 7
입력
```
2
-5 -1 5 1
-1 -5 1 5
```
예상 출력
```
36
```