# Monge와 SMAWK

Monge array는 행과 열의 최솟값 위치가 단조로 움직이는 특수한 행렬입니다. 이런 구조에서는 각 행의 최솟값을 모든 열에 대해 직접 보지 않고도 빠르게 찾을 수 있습니다. SMAWK는 totally monotone matrix에서 행 최솟값을 선형에 가깝게 구하는 알고리즘입니다.

## Monge Array

행렬 `A`가 Monge라는 것은 모든 `i1 < i2`, `j1 < j2`에 대해 아래가 성립한다는 뜻입니다.

```text
A[i1][j1] + A[i2][j2] <= A[i1][j2] + A[i2][j1]
```

직관적으로는 "왼쪽 위와 오른쪽 아래를 짝짓는 것이 교차 짝짓기보다 좋다"는 성질입니다. 이 성질이 있으면 아래 행으로 갈수록 argmin이 왼쪽으로 되돌아가지 않습니다.

## Totally Monotone

SMAWK가 요구하는 조건은 Monge보다 약한 totally monotone입니다.

```text
어떤 두 행 i1 < i2와 두 열 j1 < j2에 대해
A[i1][j1] > A[i1][j2] 이면 A[i2][j1] > A[i2][j2]
```

이 조건은 row minimum의 단조성을 보장합니다. Monge array는 totally monotone이지만, totally monotone이 항상 Monge인 것은 아닙니다.

행·열 ID는 각각 증가 순서이며 행이 있으면 열도 비어 있지 않아야 합니다. 모든 부분행렬에서 가장 왼쪽 최소 열이 아래로 갈수록 감소하지 않는 totally monotone 조건을 사용합니다. 아래 strict 부등식은 이 tie 규칙에 맞춘 방향입니다.

## 언제 쓰는가

| 문제 신호 | 접근 |
| --- | --- |
| 각 행의 최솟값 열을 찾아야 한다 | row minima |
| cost matrix가 Monge다 | SMAWK 또는 divide-and-conquer |
| DP 전이가 `min_j cost(i,j)` 행렬 형태다 | monotone optimization |
| 행/열 수가 크고 모든 값을 만들 수 없다 | implicit matrix query |

SMAWK는 행렬 값을 전부 저장하지 않고 `value(row, col)` 함수로 계산할 수 있을 때 특히 유용합니다.

## 단순 monotone row minima

SMAWK 전체 구현은 까다롭습니다. 먼저 row minimum이 단조일 때 divide-and-conquer로 찾는 구조를 이해하면 좋습니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <functional>
#include <limits>
#include <utility>
#include <vector>
using namespace std;

void monotoneRowMinima(
    int rowLeft,
    int rowRight,
    int colLeft,
    int colRight,
    const function<long long(int, int)>& value,
    vector<int>& answer
) {
    if (rowLeft > rowRight) {
        return;
    }

    int rowMid = (rowLeft + rowRight) / 2;
    pair<long long, int> best = {value(rowMid,colLeft), colLeft};
    for (int col = colLeft; col <= colRight; ++col) {
        long long current = value(rowMid, col);
        if (current < best.first) {
            best = {current, col};
        }
    }

    answer[rowMid] = best.second;
    monotoneRowMinima(rowLeft, rowMid - 1, colLeft, best.second, value, answer);
    monotoneRowMinima(rowMid + 1, rowRight, best.second, colRight, value, answer);
}
```

이 방식은 SMAWK보다 느릴 수 있지만, 단조 argmin을 쓰는 기본 패턴을 보여 줍니다.

## SMAWK 흐름

SMAWK는 두 단계를 반복합니다.

1. Column reduction: 필요 없는 열을 stack처럼 제거한다.
2. 홀수 행의 최솟값을 재귀적으로 구한다.
3. 짝수 행은 주변 홀수 행의 최솟값 범위 사이에서만 찾는다.

핵심은 totally monotone 조건 덕분에 어떤 열이 이후 행에서도 최솟값이 될 수 없음을 판정할 수 있다는 점입니다.

## SMAWK 구현 스케치

아래 코드는 개념을 보여 주는 간단한 형태입니다. 행과 열은 0-index 배열로 넘깁니다.

```cpp compile-check
#include <functional>
#include <vector>
using namespace std;

void smawk(
    const vector<int>& rows,
    const vector<int>& cols,
    const function<long long(int, int)>& value,
    vector<int>& answer
) {
    if (rows.empty()) {
        return;
    }

    vector<int> reducedCols;
    for (int col : cols) {
        while (!reducedCols.empty()) {
            int row = rows[(int)reducedCols.size() - 1];
            int lastCol = reducedCols.back();
            if (value(row, col) < value(row, lastCol)) {
                reducedCols.pop_back();
            } else {
                break;
            }
        }
        if ((int)reducedCols.size() < (int)rows.size()) {
            reducedCols.push_back(col);
        }
    }

    vector<int> oddRows;
    for (int i = 1; i < (int)rows.size(); i += 2) {
        oddRows.push_back(rows[i]);
    }
    smawk(oddRows, reducedCols, value, answer);

    int start = 0;
    for (int i = 0; i < (int)rows.size(); i += 2) {
        int row = rows[i];
        int end = (int)reducedCols.size() - 1;
        if (i + 1 < (int)rows.size()) {
            end = start;
            while (reducedCols[end] != answer[rows[i + 1]]) {
                ++end;
            }
        }

        int bestCol = reducedCols[start];
        for (int j = start; j <= end; ++j) {
            if (value(row, reducedCols[j]) < value(row, bestCol)) {
                bestCol = reducedCols[j];
            }
        }
        answer[row] = bestCol;
        start = end;
    }
}
```

실전에서는 tie-breaking, 행/열 id 압축, `value` 호출 비용을 더 세심하게 관리해야 합니다. 처음에는 monotone divide-and-conquer로 충분한지 먼저 확인하는 편이 안전합니다.

## DP와 연결

DP 전이가 아래처럼 행렬 최솟값 찾기로 바뀌면 Monge/SMAWK 후보가 됩니다.

```text
dp[i] = min_j previous[j] + cost(j, i)
```

`A[i][j] = previous[j] + cost(j, i)`라고 보면, 각 row `i`의 minimum column `j`를 찾는 문제입니다. 이 행렬이 totally monotone이면 SMAWK를 쓸 수 있습니다.

## 시간 복잡도

| 방법 | 시간 |
| --- | ---: |
| 모든 행/열 확인 | `O(RC)` |
| monotone D&C row minima | `O(R + C log(R+1))` |
| SMAWK | `O(R + C)` value calls 수준 |

SMAWK의 이론적 성능은 좋지만 구현 실수 비용도 큽니다. value 계산이 비싸면 호출 횟수 관리가 중요합니다.

## Monge에서 argmin 단조성

위 행 i의 왼쪽 최소 열 p와 아래 행 j의 왼쪽 최소 열 q가 p>q라고 가정합니다. 최소성으로 A[i,p]<=A[i,q], A[j,q]<=A[j,p]입니다. Monge 부등식은 반대 방향 합을 강제하므로 두 차이는 모두 0이어야 합니다. 그러면 위 행에서도 q가 최소여서 p가 가장 왼쪽이라는 선택과 모순입니다. 이전 DP 열별 상수를 더해도 교차 부등식에서 상쇄됩니다.