• 문제를 정리하면 구해야 하는 것은 max_(i,j){ (q[i] - p[j]) * (e[i] - d[j]) } (q[i]>p[j], e[i]>d[j]) 이다.
  • 기하학적으로 이해하면, (q,e)를 우측 상단의 점으로 (p,d)를 좌측 하단의 점으로 갖는 직사각형의 면적이다.
• q[i0]>q[i1] 이고 e[i0]>e[i1] 인 i0,i1이 있다면, i1은 최적값이 될수 없다. 따라서 제거해도 된다.
• 마찬가지로 p[j0]<p[j1] 이고 d[j0]<d[j1] 인 j0,j1 이 있다면 j1번째 원소들을 제거해도 된다.
• 필요 없는 원소들을 실제로 제거하는 것은 q값을 기준으로 스위핑하면서 O(n)에 처리할수 있다.
• 이렇게 남은 (q[i],e[i]) 들을 q값이 증가하는 순서로 정렬하면 e값은 단조감소한다. (p[j],d[i]) 들도 마찬가지.
• 그렇다면 A[i,j]=(q[i] - p[j]) * (e[i] - d[j]) 가 total monotonicity 를 갖는 것을 확인할수 있다. 식을 잘 전개해서 정리하면 Monge property 를 만족하는 것을 증명할수 있다.
  • 애초에 이 식을 직사각형의 면적으로 이해했으면, 그림을 그려봐서 직관적으로 쉽게 받아들일수 있다.
• 그러므로 이제 분할정복 최적화나 SMAWK 알고리즘를 사용하면 각 i에 대한 최댓값들을 구할수 있고, 그중에서 다시 최댓값을 찾으면 문제를 해결할수 있다.
• 이렇게 쓰고 나면 아주 간단해 보인다. 나도 그렇게 생각했다. 그러나 사소해보이지만 (그래서 다른 블로그 풀이에서는 언급도 잘 안되는..) 중요한 처리가 아직 빠져있었고.. 내 경우에는 이것을 제대로 처리하느라고 하루 이상을 날렸다..
• 문제가 되는 그 부분은, 지금 A[i,j]의 정의에서는 (q[i]>p[j], e[i]>d[j]) 이 조건이 빠져있었다는 부분이다. 이것을 처리해야 한다.
• A[i,j]가 q[i]>p[j], e[i]>d[j] 를 모두 만족할때만 (q[i] - p[j]) * (e[i] - d[j])를 갖고, 나머지 경우에는 -INF를 갖는다고 정의해보자. 이러면 몽주 어레이가 되지는 못한다. 하지만, 여전히 monotone matrix이기는 하다 (..사실 아닌데 그럴거라고 생각했다 ㅜㅜ) 그래서 분할정복 최적화를 적용하는 데에는 문제가 없어야 한다. 하지만 계속 WA를 받았다..
• 이것이 모노톤하다고 생각한 근거는, i가 주어졌을때 조건을 만족하는 j의 범위를 [l[i], r[i]] 라고 했을때, l[i]와 r[i]가 모두 단조증가한다는 이유였다. 하지만 문제가 된 이유는, l[i]>r[i]인 i가 있을수 있다는 것이었다. 다시 말하면 모든 j에 대해서 -INF값을 갖는 i가 있을 수 있다는 것이다. 이경우에 opt값을 0으로 처리하게 되면 단조성이 깨지게 된다.. (i-1이 j=2에서 최댓값을 갖더라도 찾지 못한다 ㅜㅜ)
• 그래서 사용한 해결 방법은.. 모든 i들에 대해서 l[i]와 r[i]를 구해서, 조건을 만족하는 j가 존재하는 i값들에 대해서만 최댓값을 구하는 것이었다. l[i]와 r[i]는 모두 단조증가하므로 다행히도 O(n)에 저 범위를 모두 구할수 있었다.
• 다른 코드에서 본 방법은 좀 더 신기하다.

(다이아몬드 이상은 코드 생략) * Dependency: teflib.xxx.yyy