게임 세계의 토네이도
시간 제한2초메모리 제한512 MB
최대 100000개의 축에 나란한 직사각형이 주어질 때, 이들의 합집합 넓이를 구한다.
문제
Brilliant Game Overseers(BGO)는 완전히 새로운 게임을 만들고 있다. 투자자들이 요즘은 거대한 게임 세계가 판매 포인트라고 지적했기 때문에, 그들을 만족시키려고 흥미로운 활동이 가득한 거대한 게임 세계가 계획되었다. 세계 전체를 웅장하게 담은 큰 지도 외에도, 게임 속 작은 요소들의 배치를 담은 여러 크기의 작은 지도가 설계되었다. 요소들이 어느 정도 흩어져 있어야 하므로 이 지도들은 겹칠 수 있다.
설상가상으로, 모든 지도가 막 완성된 다음 날, 토네이도가 BGO 사무실을 휩쓸고 지나갔고, 이제 원본 지도와 작은 지도 몇 장이 사라졌다. 게임을 최대한 살려내야 하는 당신은, 토네이도가 남긴 요소 지도로 원본 지도의 최대한 많은 부분을 맞춰 보라는 임무를 받았다. 다행히 모든 지도에는 좌표가 표시되어 있고 축에 정렬되어 있으므로, 남은 지도들이 덮는 영역(픽셀 단위)이 얼마나 넓은지 알아내는 것부터 시작하는 게 좋겠다고 생각한다.
입력
입력은 남아 있는 축 정렬된 직사각형 지도의 수를 나타내는 정수 n(1 ≤ n ≤ 100 000)으로 시작한다. 그다음 n개의 줄이 지도를 나타내며, 각 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 여기서 0 ≤ x1, y1, x2, y2 ≤ 109이다. x1과 y1은 직사각형의 왼쪽 아래 모서리 좌표이고, x2와 y2는 오른쪽 위 모서리 좌표이다. 즉 x1 < x2이고 y1 < y2이다.
출력
남은 지도들이 덮는 게임 세계의 총 넓이를 출력한다.