[Codeforces 651E]Table Compression

Link

For simplicity, let's assume all values are different.
For each row, we can connect edges from cells of larger values to cells of smaller values.
Considering time and memory usage, we only add edges between cells of adjacent values. (So $sorting$ is required)
For each column, we do the same thing.

Therefore, we get a $DAG$ ($Directed\ Acyclic\ Graph$), whose root is the cell of the largest value.
Each cell becomes a node in the graph.
We can know that if there is an edge from $a$ to $b$, the value of $a$ must be larger than $b$
So, the low bound of maximum number in the compressed table is the height of the whole graph.
How to reassign values of each cell?
Let's reassign each cell's (Call the cell $u$) value to the height of the subgraph, whose root is $u$.
Now that the low bound is reached.

How to calculate the height of a subgraph?
Let $DP[u]$ be the height of the subgraph, whose root is $u$.
Then we can conclude the following recursive formula:
$DP[u]=\max(DP[v]+1,v$ is a child node of $u)$
Specially, if $u$ has no child node, $DP[u]=1$
$Memorized\ Search$ can be used to obtain amortized time complexity $O(1)$.

Now it's possible to have pairs of cells of same values.
We can know:
If two cells of same value are on the same horizontal position, or same vertical position
After compression, both cells' values should still be the same.
So we can treat both cells as one single cell. (A single node in the graph)
$Disjoint\ Sets$ can be used to perform the implementation.

Time complexity：$O(NM(\log M+\log N))$ ($sorting$ of $N$ rows and $M$ columns)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
int N,M;
int GRID[1000000],DJ[1000000];
int Find(const int a){return DJ[a]==a?a:(DJ[a]=Find(DJ[a]));}
void MergeSameValues()
{
    for(int i=0;i<N*M;i++)DJ[i]=i;
    vector<int>s;
    for(int i=0;i<N;i++)
    {
        s.clear();
        for(int j=0;j<M;j++)s.push_back(i*M+j);
        sort(s.begin(),s.end(),[](const int a,const int b)->bool{return GRID[a]<GRID[b];});
        for(int j=1;j<M;j++)if(GRID[s[j-1]]==GRID[s[j]])DJ[Find(s[j-1])]=Find(s[j]);
    }
    for(int i=0;i<M;i++)
    {
        s.clear();
        for(int j=0;j<N;j++)s.push_back(j*M+i);
        sort(s.begin(),s.end(),[](const int a,const int b)->bool{return GRID[a]<GRID[b];});
        for(int j=1;j<N;j++)if(GRID[s[j-1]]==GRID[s[j]])DJ[Find(s[j-1])]=Find(s[j]);
    }
    vector<int>().swap(s);
}
vector<int>ET[1000000];
void BuildGraph()
{
    for(int i=0;i<N*M;i++)ET[i].clear();
    vector<int>s;
    for(int i=0;i<N;i++)
    {
        s.clear();
        for(int j=0;j<M;j++)s.push_back(i*M+j);
        sort(s.begin(),s.end(),[](const int a,const int b)->bool{return GRID[a]<GRID[b];});
        for(int j=1;j<M;j++)if(GRID[s[j-1]]!=GRID[s[j]])ET[Find(s[j])].push_back(Find(s[j-1]));
    }
    for(int i=0;i<M;i++)
    {
        s.clear();
        for(int j=0;j<N;j++)s.push_back(j*M+i);
        sort(s.begin(),s.end(),[](const int a,const int b)->bool{return GRID[a]<GRID[b];});
        for(int j=1;j<N;j++)if(GRID[s[j-1]]!=GRID[s[j]])ET[Find(s[j])].push_back(Find(s[j-1]));
    }
    vector<int>().swap(s);
}
int DP[1000000];
int GetDP(const int u)
{
    int &ans=DP[u];
    if(ans!=-1)return ans;
    ans=1;
    for(const int nxt:ET[u])getmax(ans,GetDP(nxt)+1);
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)for(int j=0;j<M;j++)scanf("%d",&GRID[i*M+j]);
        MergeSameValues();
        BuildGraph();
        for(int i=0;i<N*M;i++)DP[i]=-1;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                if(j)putchar(' ');
                printf("%d",GetDP(Find(i*M+j)));
            }
            puts("");
        }
    }
    return 0;
}