Codeforces Round #345 (Div. 2) E. Table Compression（并查集）

传送门

首先先从小到大排序，如果没有重复的元素，直接一个一个往上填即可，每一个数就等于当前行和列的最大值 + 1

如果某一行或列上有重复的元素，就用并查集把他们连起来，很（不）显然，处于同一行或列的相同元素始终应该保持一样的，然后再一个一个往上填

#include <bits/stdc++.h>
#define N 1000007
#define fi first
#define se secondusing namespace std;pair <int, pair<int, int> > A[N];
map <int, int> X, Y;int n, m;
int Hx[N], Hy[N], ans[N], f[N];inline int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}inline void uni(int x, int y)
{
x = find(x);
y = find(y);
if(x != y) f[x] = y;
}int main()
{
int i, j = -1, k, x, y, p;
scanf("%d %d", &n, &m);
for(i = 0; i < n * m; i++)
{
f[i] = i;
scanf("%d", &A[i].first);
A[i].se.fi = i / m;
A[i].se.se = i % m;
}
sort(A, A + n * m);
for(i = 0; i < n * m; i++)
{
if(i != n * m - 1 && A[i].fi == A[i + 1].fi) continue;
for(k = j + 1; k <= i; k++)
{
x = A[k].se.fi;
y = A[k].se.se;
p = A[k].se.fi * m + A[k].se.se;
Hx[x] = p;
Hy[y] = p;
}
for(k = j + 1; k <= i; k++)
{
x = A[k].se.fi;
y = A[k].se.se;
p = A[k].se.fi * m + A[k].se.se;
uni(Hx[x], p);
uni(Hy[y], p);
}
for(k = j + 1; k <= i; k++)
{
x = A[k].se.fi;
y = A[k].se.se;
p = A[k].se.fi * m + A[k].se.se;
p = find(p);
ans[p] = max(ans[p], max(X[x], Y[y]) + 1);
}
for(k = j + 1; k <= i; k++)
{
x = A[k].se.fi;
y = A[k].se.se;
p = A[k].se.fi * m + A[k].se.se;
p = find(p);
X[x] = max(X[x], ans[p]);
Y[y] = max(Y[y], ans[p]);
}
j = i;
}
for(i = 0; i < n * m; i++)
{
printf("%d ", ans[find(i)]);
if(i % m == m - 1) puts("");
}
return 0;
}