CF2201F2 Monotone Monochrome Matrices (Hard Version) 题解

linjunye · 2026-02-25 11:35:15 · 题解

首先先发掘一些性质。你发现，如果这个矩阵不合法，那么我任意交换两行或者两列，得到新的矩阵也不合法。如果这个矩阵合法，那么我任意交换两行或两列，得到新的矩阵也是合法的。

那我考虑把合法的矩阵变成一个好做的性质。你发现我们可以通过若干次行、列交换把矩阵变成这样：

即，第 i 行不比第 i-1 行 1 的数量少，每一行的 1 都能组成一个前缀。

反之，如果矩阵不合法，那么一定不能变成这个样子。

我们考虑对这个东西计数。很显然我们对每一行的 1 的个数可以用哈希映射一下，然后我们该怎么判断合法呢？我们先看看不合法长什么样：

那我们试着把每一列的 1 从下往上填充，就变成这样：

然后映射每一行 1 的个数，对所有行的哈希值求和，如果和原来的值不一样，那么两个图就不一样，不合法。

既然可以判断，我们开始证明行、列交换不会影响哈希的值。

先考虑行交换，这是显然可以的。

再考虑列交换，你发现这不会改变该所有行 1 的个数，且每一列都是独立的，对“向下对齐”的图也不会产生影响。

所以，哈希可行。函数你想怎么定义就怎么定义，我定义的是 f(x)=\frac{x(x-1)}{2}。当然可以用更保守的，比如 f(x)=8x^3+x^2+x\oplus val，看你喜欢哪个。

#include<bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
const int N=10000010;
const int mod=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int n,m;
int x,y;
int cntc[N],cntr[N];
int cnt[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cnt[i]=cntc[i]=cntr[i]=0;
    int sc=0,sr=0;
    while(m--){
        int x,y;cin>>x>>y;
        sr+=cntr[x];//行
        cntr[x]++;
        sc+=cnt[++cntc[y]];//列，记录size可以实现向下对齐
        cnt[cntc[y]]++;
        if(sr==sc)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Tc=1;
    cin>>Tc;
    while(Tc--)solve();
    return 0;
}
/*

*/