题解【CF1606D】

· · 题解

很套路的一个题。

显然，纵列的切割只有 m-1 种方案。

由题意，经切割后，左边矩阵蓝色部分的最大值一定小于左边矩阵红色部分的最小值。弱化这个条件，只考虑第一列，将第一列的数字从小到大排序，以此重组矩阵中每一行的顺序。此时如果第 i 行第一格为蓝色，第 i+1 行第一格为红色，那么 1 \sim i 行第一列均为蓝色，(i+1) \sim n 行第一格均为红色。于是枚举这个 i，由于 i 最多只能取 n-1。所以需要枚举的情况总数为 (n-1)(m-1)，接下来只需 O(1) 验证即可。

显然，若切割前 i 行，前 j 列，只需保证切割后的左上部最大值小于左下部最小值并且右上部最小值大于右下部最大值，即可得到一组合法解。这四个量可以用前缀和与后缀和计算。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int T,n,m,p[N];char ans[N];
vector<int>a[N],fmn[N],fmx[N],gmn[N],gmx[N],zsmx[N],zxmn[N],ysmn[N],yxmx[N];
//p[i]表示排完序后的第i个是第几行
//fmn表示每行的前缀最小，同理fmx（这里的前缀以排完序后的矩阵来算，一下同理）
//gmn表示每行的后缀最小，同理gmx
//zxmn表示位置(i,j)左下部的最小值
//zsmx表示位置(i,j)左上部的最大值
//ysmn表示位置(i,j)右上部的最小值
//yxmx表示位置(i,j)右下部的最大值
bool cmp(int x,int y){
    return a[x][1]<a[y][1];
}
int main(){
    for(cin>>T;T;T--){
        cin>>n>>m;
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=m+1;j++){
                a[i].push_back(0);
                fmn[i].push_back(1e6+5);
                gmn[i].push_back(1e6+5);
                fmx[i].push_back(0);
                gmx[i].push_back(0);
                zsmx[i].push_back(0);
                zxmn[i].push_back(1e6+5);
                ysmn[i].push_back(1e6+5);
                yxmx[i].push_back(0);
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        for(int i=1;i<=n+1;i++)
            p[i]=i;
        sort(p+1,p+n+1,cmp);
        for(int j=1;j<=m;j++){
            for(int i=1;i<=n;i++){
                fmx[p[i]][j]=max(a[p[i]][j],fmx[p[i-1]][j]);
                fmn[p[i]][j]=min(a[p[i]][j],fmn[p[i-1]][j]);
            }
            for(int i=n;i>=1;i--){
                gmx[p[i]][j]=max(a[p[i]][j],gmx[p[i+1]][j]);
                gmn[p[i]][j]=min(a[p[i]][j],gmn[p[i+1]][j]);
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                zsmx[p[i]][j]=max(zsmx[p[i]][j-1],fmx[p[i]][j]);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=1;j--)
                ysmn[p[i]][j]=min(ysmn[p[i]][j+1],fmn[p[i]][j]);
        for(int i=n;i>=1;i--)
            for(int j=1;j<=m;j++)
                zxmn[p[i]][j]=min(zxmn[p[i]][j-1],gmn[p[i]][j]);
        for(int i=n;i>=1;i--)
            for(int j=m;j>=1;j--)
                yxmx[p[i]][j]=max(yxmx[p[i]][j+1],gmx[p[i]][j]);
        int t1=-1,t2=-1;
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                if(zsmx[p[i]][j]<zxmn[p[i+1]][j]&&ysmn[p[i]][j+1]>yxmx[p[i+1]][j+1]){
                    t1=i,t2=j;break;
                }
        if(t1==-1)puts("NO");
        else{
            puts("YES");
            for(int i=1;i<=t1;i++)ans[p[i]]='B';
            for(int i=t1+1;i<=n;i++)ans[p[i]]='R';
            for(int i=1;i<=n;i++)putchar(ans[i]);
            printf(" %d\n",t2);
        }
        for(int i=0;i<=n+1;i++){
            a[i].clear();
            fmn[i].clear(),gmn[i].clear(),fmx[i].clear(),gmx[i].clear();
            zsmx[i].clear(),zxmn[i].clear(),ysmn[i].clear(),yxmx[i].clear();
        }
    }
    return 0;
}