BOJ 17975 - Strike Zone

BOJ 17975 - Strike Zone

금광세그로 날먹할 수 있긴한데, $x, y$가 모두 달라서 더 쉬운 방법(?)으로 풀 수 있기 때문에 그 방법을 설명한다.

동일하게 Segment Tree + Sweeping인데, 금광처럼 Node의 Merge연산을 기발하게 가져가야하는건 아니다.

SolutionPermalink

$2$차원 평면에서 파란점의 위치엔 $c_1$을 표시해주고 빨간점의 위치엔 $-c_2$ 를 모두 표시해준다고 해보자.

그럼 이 문제는 $2$차원 평면에서 구간의 합이 가장 큰 직사각형을 찾는 문제로 치환된다.

직사각형의 넓이가 $0$이여도 상관없다. 그냥 $2$차원의 어떤 영역이라고 생각하자.

일단 모든 점을 좌표압축을 해주고 $x$좌표의 개수가 $X$, $y$좌표의 개수가 $Y$라고 하자.

정답이 되는 어떤 직사각형은 항상 왼쪽 모서리에 파란 점을 포함한다.

그 점을 $p_0(y_0, x_0)$ 이라고 한다.

$dp_{u,i}~~(x_0 \le i < X)$ 를 $[y_0, x_0] \times [\infty, i]$ 영역에서 값이 최대인 직사각형이라고 해보자.

최대값을 관리하는 Lazy Segment Tree를 이용하면 $i$ 를 방문했을 때, $[y_i, \infty)$ 구간에 그 점이 파란색이라면 $c_1$을, 빨간색이라면 $-c_2$를 더해준다.

그 점을 포함하는 직사각형이 되려면 높이가 최소 $y_i$ 가 되야하기 때문이다.

그럼 이제 $dp_{u,i}=$ $[y_i, \infty)$ 구간에서의 최대값이므로 트리에 쿼리를 날리면 된다.

이처럼 $dp_{d, i}$도 구해준다. $dp_{d, i}$ 는 위 직사각형이 아닌 아래 직사각형이다.

그럼 $p_0$ 를 왼쪽 모서리로 가지는 직사각형중 가장 큰 값은

$Max_{x_0 \le i < X} \{dp_{u,i}+dp_{d,i}-c_0\}$ 이다.

$c_0=$$p_0$의 값

이는 시간복잡도 $O(N^2\log N)$에 구현된다.