BOJ 7626 직사각형

이 문제는 segment tree lazy propagation을 연습해볼 문제로 추천받은 문제인데,

아무리 생각해도... 어떻게 segment tree를 활용할지 떠오르지가 않는다.

일단 이 문제는 좌표위에 여러 직사각형들이 차례로 주어지는데, 범위는 무려 0부터 10의 9제곱까지... 그리고 이 직사각형들이 좌표평면을 덮는 면적을 구하는 문제이다. 즉 겹치든 말든 일단 좌표평면을 얼마나 덮는지 구하는 문제이다. 그리고 직사각형은 20만개가 들어온다.

일단 x좌표를 기준으로...하는 것은 메모리 초과이다. 

잘 생각해보자. 세그먼트 트리는 구간합이나 구간의 최소, 최대값을 O(log N)만에 구할 수 있고, 업데이트 또한 O(log N)만에 할 수 있는 자료구조이다. 

이 문제에서는 왠지 구간합을 구해야 할 것 같은데, 단순히 구간합만 구할 것이라면 굳이 세그먼트 트리와 lazy propagation을 쓸 필요가 없을 것이다. 

업데이트가... 그것도 구간 업데이트가 빈번히 있을 가능성이 큰데.. 입력을 잘 보면 직사각형을 구성하는 x좌표의 구간, y좌표의 구간이 주어진다.

하지만 각 구간을 일일이 업데이트 한다고 생각해보면... 일단 범위가 너무 커서 segment tree를 만들 수 없다. 좌표 압축? 내가 좌표 압축을 해본적이 없기도 하지만... 이 문제에서는 면적을 구해야하는데, 만약 좌표 압축을 한다면 직사각형의 각 변의 길이나 넓이를 따로 기록해 둬야하나?...음...