링크

문제 요약

2차원 평면에 x축과 y축에 평행하게 직사각형 모양 색종이가 놓여져 있다. 쿼리로 직사각형이 주어질 때, 해당 범위에서 색종이가 가장 많이 겹쳐 있는 영역에 놓인 색종이의 장 수를 출력하는 문제이다.

관찰

문제의 조건을 잘 살펴보자. 보면 격자의 범위가 1500 by 1500 으로 굉장히 작은 편임을 알 수 있다. 따라서 2차원 누적합의 아이디어를 이용하면 각 격자마다 몇장의 종이가 겹쳐있는지를 $O(1500^2)$ 에 쉽게 알 수 있다. 이제 종이가 깔린 상태는 알았으니 쿼리에 대한 답변만 빠르게 하면 문제가 풀릴 것이다.

풀이

2차원에서 2차원 최댓값을 구하는 문제는 당연히 2차원 최댓값 세그먼트 트리를 구축하면 풀릴 것이다. 만약 2차원 최댓값 세그먼트 트리가 구축되었다고 가정하면, 하나의 직사각형 쿼리를 처리하는데 $O(\log^2{1500})$ 의 시간이 걸릴 것이다. 문제는 2차원 세그를 구축하는데 최적화가 필요하단 것이다.

1차원 세그먼트 트리를 구축하는데 걸리는 시간은 단순히 update 연산을 이용할 경우 $O(N\log{N})$의 시간이 걸리고, 트리의 리프부터 한층씩 계산하는 방식은 $O(N)$ 임이 잘 알려져 있다. 이 아이디어를 그대로 차용하면 2차원 세그도 $O(N^2)$ 의 시간에 구축이 가능하고, 이 문제의 경우 $O(1500^2)$ 의 시간이 걸림이 자명하다. 따라서 본 문제를 해결하는 전체 시간 복잡도는 $O(1500^2+M\log^2{1500})$ 이다.