# 2. 题解

（要找借口也不是没有——在很久很久以前我看到这题觉得好难啊然后就一直没做今天补了一个千年老坑是吧就发混更一下了）

$L(i, j)=min(L(next _ i, next _ j))$
$R(i, j)=max(R(next _ i, next _ j))$

#include <bits/stdc++.h>

#define NS (505)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int n, m, h[NS][NS], l[NS][NS], r[NS][NS];

void Dfs(int a, int b)
{
if (l[a][b]) return;
l[a][b] = INT_MAX, r[a][b] = INT_MIN;
if (a < 1 || a > n || b < 1 || b > m) return;
if (a == n) l[a][b] = r[a][b] = b;
for (int i = 0; i < 4; i += 1)
if (h[a][b] > h[a + dx[i]][b + dy[i]])
{
Dfs(a + dx[i], b + dy[i]);
l[a][b] = min(l[a][b], l[a + dx[i]][b + dy[i]]);
r[a][b] = max(r[a][b], r[a + dx[i]][b + dy[i]]);
}
}

PII e[NS], st[NS];

int main(int argc, char const* argv[])
{
IN(n), IN(m);
for (int i = 1; i <= n; i += 1)
for (int j = 1; j <= m; j += 1)
IN(h[i][j]);
for (int i = 1; i <= m; i += 1) Dfs(1, i);
int cnt = 0;
for (int i = 1; i <= m; i += 1) if (!l[n][i]) cnt++;
if (cnt) printf("0\n%d\n", cnt), exit(0);
for (int i = 1; i <= m; i += 1) e[i].FIR = l[1][i], e[i].SEC = r[1][i];
sort(e + 1, e + 1 + m);
for (int i = 1; i <= m; i += 1)
if (e[i].FIR <= e[i].SEC)
{
if (e[i].FIR == 1) st[cnt = 1] = e[i];
else
{
if (e[i].SEC <= st[cnt].SEC) continue;
while (cnt >= 2 && st[cnt - 1].SEC + 1 >= e[i].FIR) cnt--;
st[++cnt] = e[i];
}
}
printf("1\n%d\n", cnt);
return 0;
}