문제

• 
• 시간 제한: 1초
• 메모리 제한: 512MB

Problem Analysis

각 cell 별로 종이의 수를 구하고, 범위 내에서 최대를 빠르게 구하기 위해 Segment Tree를 이용하면 된다.

그러나, Navie 하게 색종이가 주어질 때마다 위와 같이 해당 영역에 값을 더하면, 전처리 과정에서만 너무 많은 시간을 소모한다. 여기서 문제는, 최악의 경우 하나의 cell를 N 번 방문하는 것이 문제인데, 각 cell을 중복해서 방문하는 것을 최소화하는 것이 관건이다.

Algorithm

위와 같이 종이가 주어졌을 때, 각 네 구역에 1과 -1 중 하나를 적절히 기입한다. 다음으로, 오른쪽으로 누적합을 구한다. 이후, 아래로 누적합을 구한다. 다음으로, 2D segment tree를 구현하여, 구간별 최대를 구한다.

Data Structure

• ST[][]: max를 구하는 two-dimensional segment tree
• board[][]: 종이가 올려진 상황을 저장

결과

Other

시간 복잡도는 전처리에 O(L^2). 매 쿼리마다 O(logL*logL) 이다. (L == 1500)