직사각형
시간 제한2초메모리 제한512 MB
흰 배경에 최대 100,000개의 축에 평행한 직사각형을 XOR 방식으로 그릴 때, 최종적으로 검은색이 되는 픽셀 수를 구한다.
문제
새 그래픽 시스템을 개발하는데, 새로운 기능이 추가되었다. 도형을 그리면 그 도형에 포함된 모든 픽셀이 흰색에서 검은색으로, 또는 검은색에서 흰색으로 뒤집힌다. 흰색 화면 위에 겹치는 직사각형 세 개를 그리면 다음과 같이 된다:
흰 화면에서 시작하여 축에 나란한 일련의 직사각형이 주어질 때, 마지막에 검은색이 되는 픽셀은 몇 개인가?
입력
각 입력은 하나의 테스트 케이스로 이루어진다. 프로그램이 서로 다른 입력으로 여러 번 실행될 수 있다.
각 테스트 케이스의 첫째 줄에는 직사각형의 개수를 나타내는 정수 n (1 ≤ n ≤ 100,000)이 주어진다.
다음 n개의 줄 각각에는 직사각형의 서로 맞은편 모서리를 나타내는 네 개의 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 10^9, 0 ≤ y1 < y2 ≤ 10^9)가 공백으로 구분되어 주어진다. 직사각형은 x1 ≤ x < x2, y1 ≤ y < y2를 만족하는 모든 픽셀 (x, y)로 이루어지므로 면적은 (x2 - x1) × (y2 - y1) 픽셀이다.
출력
흰 화면에 모든 직사각형을 그린 뒤 검은색이 되는 픽셀의 개수를 정수 하나로 출력한다.