• '금광세그'라는 테크닉의 어원이 되는 바로 그 문제이다.
  • 세그먼트 트리를 이용해서 최대 부분 합을 구하는 테크닉이다.
• 아직 저 테크닉이 웰노운이 아닐 시기에 KOI 중등부 문제로 출제되었고, 현장에서 만점을 받은 사람이 아무도 없었다고 한다. 그 이후 '금광세그'라는 이름으로 엄청나게 유명해졌고, 현재 저 테크닉은 한국인들에게 유독 널리 알려진 테크닉으로 평가된다고 한다…
• 하지만.. 이 문제는 최대 부분 합 외에도 여러가지 테크닉이 상당히 필요한 문제이다.
• 당장 문제를 최대 부분합 문제로 바꿔 생각하는 것도 그렇게 쉽지는 않고 (최대 부분합 문제로 바꾸어도 아직도 좀 무식하게 문제를 푸는 듯한 느낌이 들어서 정해가 아닌것 같은 착각에 빠지는 부분도 있다..), 좌표 압축도 해야 하고.., 파이썬으로 제출할 경우에는 PyPy로도 시간제한이 빡빡해서 구현에도 신경을 써야 한다..
• 우선 최대 부분합 문제로 바꾸는 방법. 만약 y축으로는 모든 범위이고, x 축으로의 바운더리만 잡아야 하는 문제였다면, y좌표를 무시하고 포인트들을 그냥 1차원 직선상의 점들이라고 생각해도 되니까 그냥 모든 점을 집어넣은 뒤에 최대 부분합을 구하면 된다. n개의 점을 포함하는 세그트리를 O(n)에 만들고 최대 부분합을 O(logn)으로 한번만 구하면 되니까 전부 O(n + logn)에 풀린다
• 그러면, 문제가 y0는 가장 북쪽의 있는 점의 y좌표로 고정되어 있고, x0, x1, y1만 구해야 하는 문제였다면? 포인트를 y축 기준으로 정렬시켜서, 하나씩 추가시키면서 그때마다 최대 부분합을 계산해서, 그중의 최댓값을 구하면 된다. 여기까지 확장하는것도 어렵지 않다. 점 추가 (포인트 업데이트)를 n번, 부분합쿼리를 n번 돌리니까 O(nlogn)에 풀린다.
• 그러면 여기에서 y0이 고정되어있다는 조건만 제거하면 원래 문제가 된다. 이것은 그냥 윗 과정을 모든 가능한 y0에 대해서 수행하면 된다. y0의 후보가 n개이니까, 위의 과정을 n번 돌리면 O(n^2logn)에 풀린다.
  • 사실 이 부분이 좀 무식해보이는 부분이고.. 더 효율적인 방법이 있을것도 같지만.. 그냥 이게 정해라고 하는 것 같다..
• 기본 아이디어는 이것이고, 이제 구현하는데에 필요한 디테일들..
• (x0,y0)에 w를 가진 점을 세그트리에 추가한다면, arr[x0]에 w를 더하는 식으로 처리하게 될것이지만, x의 범위가 10^9이므로 그대로 처리하기엔 메모리가 부족하다. 좌표 압축이 필요하다.
• y축을 따라서 스위핑할때, y값이 같은 점들은 동시에 들어가야 한다. 그냥 매번 한개씩 추가하는것보다 약간 더 귀찮다.
• 시간 제한이 3초이긴 하지만, 처음에는 PyPy로도 시간 초과를 받았다. 시간을 줄이려고 몇가지 잡스러운 최적화를 시도했지만 모두 실패. 효과가 있었던 방법은, 이 문제에서 구간 쿼리를 할때에는 전체 범위에 대해서만 쿼리를 하게 된다는 점에 착안한것. 전체 범위에 대한 대표값은 보통의 재귀 세그먼트 트리에서는 루트 노드가 갖고 있기 때문에 O(1)에 가져올수 있다. Teferi library 에서 사용하는 비재귀 구현에서는 메모리를 정확히 2*n만 사용하게 구현되어있고, 이 구조에서는 전체 범위를 관리하는 노드가 존재하지 않는다. 그러나 노드 수를 2^k로 맞춰서 퍼펙트 바이너리 트리 형태가 되게 하면, 저 구현에서도 루트노드가 전체 범위를 관리하게 된다. 그러면 여기에서도 전체 구간의 대표값을 루트 노드에 저장된 값을 가져와서 O(1)에 처리할 수 있다. n^2번의 업데이트 쿼리와 최대 부분합 쿼리를 둘다 O(logn)에 처리 하던 것에서, 업데이트 쿼리만 O(logn)에 처리하면 되므로 시간이 확 줄어든다. 결국 6초정도의 시간으로 통과했다.

(다이아몬드 이상은 코드 생략)

• Dependency: teflib.segmenttree.SegmentTree