拓扑序
首先可以明确无论怎么交换行列，原本在同一行或者同一列的元素，还是会处于同一行或者同一列
- 条件一
每行每行地看，如果能满足从小到大的条件，说明第 \(i\) 行的值域 \([min_i, max_i]\) 与 第 \(i - 1\) 行的值域 \([min_{i - 1}, max_{i - 1}]\) 必然有以下关系：
\(max_{i - 1} \le min_i\)
因此提出每一行的值域范围，判断一下是否满足该条件，如果碰到 \(0\) 可以直接跳过，如果该行全 \(0\) 的话，记得特判一下（丢掉）
- 条件二
在同一行里，如果想做到从小到大，必然有一个偏序关系：如果有 \(a_{ij} < a_{ik}\)，那么第 \(j\) 列肯定在第 \(k\) 列的前面。因此对于每一行中的偏序关系都构建出来，如果这个偏序关系有拓扑序，则说明有解
记得要跳过 \(0\)
还有一个要处理的地方就是，如果同一行内有若干个数字等于 \(x\)，有若干个数字等于 \(x + 1\)，则构建偏序关系的时候是要两两相连的，显然复杂度会退化成 \(O((nm)^2)\)
我的处理方式是缩点，然后构建边，就变成了 \(O(nm)\)
其实这题总结下来就是列和行的拓扑序若能保证，则有解
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <deque>
#include <stack>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const ll maxn = 2e6 + 10;
const ll inf = 1e17 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m, 0)), gra(m + n * m);
vector<int> in(m + n * m, 0);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
cin >> matrix[i][j];
vector<array<int, 2>>leg(n);
int tp = m - 1;
for(int i=0; i<n; i++)
{
leg[i] = {n * m * 2, 1};
int cnt = 0;
for(int j=0; j<m; j++)
{
cnt += matrix[i][j] == 0;
if(matrix[i][j] == 0) continue;
leg[i][0] = min(leg[i][0], matrix[i][j]);
leg[i][1] = max(leg[i][1], matrix[i][j]);
}
if(cnt == m) leg[i] = {1, 1};
vector<array<int, 2>>a(m);
for(int j=0; j<m; j++) a[j] = {matrix[i][j], j};
sort(a.begin(), a.end());
int l = 0, r = 0;
while(l < m && a[l][0] == 0) l++;
r = l;
int pre = 0;
while(l < m)
{
while(r < m && a[l][0] == a[r][0]) r++;
tp++;
for(int j=l; j<r; j++)
{
gra[a[j][1]].push_back(tp);
in[tp]++;
}
if(pre) for(int j=l; j<r; j++)
{
gra[pre].push_back(a[j][1]);
in[a[j][1]]++;
}
l = r;
pre = tp;
}
}
sort(leg.begin(), leg.end());
int f = 1, now = 0;
for(auto [l, r] : leg)
{
if(l < now) f = 0;
now = r;
}
queue<int>q;
for(int i=0; i<=tp; i++) if(in[i] == 0) q.push(i);
while(q.size())
{
int now = q.front();
q.pop();
for(int nex : gra[now])
{
in[nex]--;
if(in[nex] == 0) q.push(nex);
}
}
for(int i=0; i<=tp; i++) if(in[i] > 0) f = 0;
if(f) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}