Tsukuru

· · 题解

宝宝题。

直接枚举 k。考察左侧矩阵，此时蓝色行的 \max 小于红色行的 \min，枚举蓝色 \max 所在的行，\max 比他大的行都应为红色，判断这些行的 \min 是否大于该行的 \max 即可，具体实现把行按照 \max 排序，求出前缀行 \max 的 \max 和后缀行 \min 的 \min，判断是否存在一个位置满足前缀 \max 小于后缀 \min。存在那么此时左侧合法，右侧同理。整体合法需要满足左侧红蓝状态等于右侧红蓝状态并且左右各自合法，所以我们把左右两侧所有合法状态的红蓝状态直接哈希判断是否有相等的即可。做完了。复杂度 O(nm\log n)。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 5e5 + 10;
const ull P1 = 1e9 + 123;
const ull P2 = 1e9 + 9;
ull BASE1, BASE2, pw1[N], pw2[N];
int n, m;
vector<int> A[N], mnl[N], mxl[N], mnr[N], mxr[N];
int pre[N], suf[N];
int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    random_device rd; mt19937 Rand(rd());
    int _; cin >> _;
    while (_ --) {
        BASE1 = Rand() % 1000 + 3, BASE2 = Rand() % 1000 + 5;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++) 
            A[i].resize(m + 2), mnl[i].resize(m + 2), mxl[i].resize(m + 2), 
            mnr[i].resize(m + 2), mxr[i].resize(m + 2);
        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) 
                cin >> A[i][j];
        for (int i = 1; i <= n; i ++) {
            mnl[i][0] = 1e9, mxl[i][0] = 0;
            for (int j = 1; j <= m; j ++) 
                mnl[i][j] = min(mnl[i][j - 1], A[i][j]), 
                mxl[i][j] = max(mxl[i][j - 1], A[i][j]);
            mnr[i][m + 1] = 1e9, mxr[i][m + 1] = 0;
            for (int j = m; j >= 1; j --) 
                mnr[i][j] = min(mnr[i][j + 1], A[i][j]), 
                mxr[i][j] = max(mxr[i][j + 1], A[i][j]);
        }
        pw1[0] = pw2[0] = 1; ull sum1 = 0, sum2 = 0;
        for (int i = 1; i <= n; i ++) 
            pw1[i] = pw1[i - 1] * BASE1 % P1, 
            pw2[i] = pw2[i - 1] * BASE2 % P2,
            sum1 += pw1[i], sum2 += pw2[i];
        sum1 %= P1, sum2 %= P2;
        bool flag = false; string Ans; Ans.resize(n); int Ansk = 0;
        for (int k = 1; k < m; k ++) {
            set< pair<ull, ull> > lft;
            vector< pair<int, int> > vec;
            for (int i = 1; i <= n; i ++) vec.push_back({mxl[i][k], i});
            sort(vec.begin(), vec.end()); pre[0] = 0, suf[n + 1] = 1e9;
            for (int i = 1; i <= n; i ++) 
                pre[i] = max(pre[i - 1], mxl[vec[i - 1].second][k]);
            for (int i = n; i >= 1; i --) 
                suf[i] = min(suf[i + 1], mnl[vec[i - 1].second][k]);
            ull sta1 = sum1, sta2 = sum2;
            for (int i = 1; i < n; i ++) {
                int p = vec[i - 1].second; 
                sta1 = (sta1 + P1 - pw1[p]) % P1, sta2 = (sta2 + P2 - pw2[p]) % P2;
                if (pre[i] < suf[i + 1]) lft.insert({sta1, sta2});
            }
            vec.clear();
            for (int i = 1; i <= n; i ++) 
                vec.push_back({mxr[i][k + 1], i});
            sort(vec.begin(), vec.end()); pre[0] = 0, suf[n + 1] = 1e9;
            for (int i = 1; i <= n; i ++) 
                pre[i] = max(pre[i - 1], mxr[vec[i - 1].second][k + 1]);
            for (int i = n; i >= 1; i --) 
                suf[i] = min(suf[i + 1], mnr[vec[i - 1].second][k + 1]);
            sta1 = 0, sta2 = 0;
            for (int i = 1; i < n; i ++) {
                int p = vec[i - 1].second; 
                sta1 = (sta1 + pw1[p]) % P1, sta2 = (sta2 + pw2[p]) % P2;
                if (pre[i] < suf[i + 1] && lft.find({sta1, sta2}) != lft.end()) {
                    flag = true; Ansk = k;
                    for (int j = 0; j < i; j ++) Ans[vec[j].second - 1] = 'R';
                    for (int j = i; j < n; j ++) Ans[vec[j].second - 1] = 'B';
                }
            }
            if (flag) break;
        }
        if (flag) cout << "YES\n" << Ans << " " << Ansk << "\n";
        else cout << "NO\n";
        for (int i = 1; i <= n; i ++) 
            A[i].clear(), mnl[i].clear(), mnr[i].clear(), 
            mxl[i].clear(), mxr[i].clear();
    }
    return 0;
}