Monotone Monochrome Matrices (Medium Version)

Treat black as $1$ and white as $0$. The bad configuration in the statement is exactly a $2\times2$ checkerboard:

$$\begin{matrix} 1&0\\ 0&1 \end{matrix} \quad\text{or}\quad \begin{matrix} 0&1\\ 1&0 \end{matrix}.$$

For each row $i$, define $S_i$ as the set of columns where row $i$ is black.

Consider two rows $i,j$. A checkerboard exists between them iff there is one column in $S_i\setminus S_j$ and another column in $S_j\setminus S_i$. If both differences are nonempty, the two chosen columns form one of the two checkerboards depending on their order. If one difference is empty, then one set contains the other, and these two rows can never form a checkerboard.

So the whole matrix is monotone iff the row sets form a chain by inclusion:

$$\forall i,j,\quad S_i\subseteq S_j\text{ or }S_j\subseteq S_i.$$

Checking all pairs directly would be very dead, so we count a certificate instead.

For two rows define

$$d(i,j)=\min(|S_i|,|S_j|)-|S_i\cap S_j|.$$

This is always nonnegative, because an intersection cannot be larger than the smaller set. Also, $d(i,j)=0$ exactly when the smaller row set is contained in the larger one. Therefore the matrix is monotone iff

$$D=\sum_{i<j} d(i,j)=0.$$

Now split $D$ into two sums:

$$D=P-I,$$

where

$$P=\sum_{i<j}\min(|S_i|,|S_j|), \qquad I=\sum_{i<j}|S_i\cap S_j|.$$

Maintain $I$ by columns. If column $c$ currently has $y$ black cells, adding a new black cell in that column creates exactly $y$ new shared-column contributions with previous black rows in that column. So

$$I\gets I+y.$$

Maintain $P$ by row sizes. Suppose row $r$ currently has size $x$, and after the update it becomes $x+1$. For another row with size $b$,

$$\min(x+1,b)-\min(x,b)= \begin{cases} 1,& b\ge x+1,\\ 0,& b<x+1. \end{cases}$$

So $P$ increases by the number of rows whose current size is at least $x+1$. Let $ge[k]$ store the number of rows with at least $k$ black cells. Since row $r$ currently has only $x$ cells, it is not included in $ge[x+1]$, which is perfect. Then after using it, increment $ge[x+1]$ because row $r$ now reaches that threshold.

For an update $(r,c)$:

$$D\gets D+ge[row[r]+1]-col[c].$$

Then update:

$$row[r]\gets row[r]+1, \quad ge[row[r]]\gets ge[row[r]]+1, \quad col[c]\gets col[c]+1.$$

The answer is YES iff $D=0$. If $D>0$, at least one row pair is not nested, so a checkerboard exists. No vibes, no sorting, no matrix storage. Just the invariant doing its job.

Correctness proof.

First, for any pair of rows $i,j$, they violate monotonicity iff $S_i$ and $S_j$ are incomparable. If they are incomparable, pick $a\in S_i\setminus S_j$ and $b\in S_j\setminus S_i$; the two columns $a,b$ form a checkerboard. Conversely, any checkerboard gives one column in each of those two differences, so the sets are incomparable.

Second, for every pair $i,j$, $d(i,j)=0$ iff $S_i$ and $S_j$ are comparable. Since every $d(i,j)\ge0$, the total $D=0$ iff every pair has $d(i,j)=0$, iff every pair of rows is comparable, iff the matrix is monotone.

Third, the maintained value of $I$ is exact because each column independently contributes one to $|S_i\cap S_j|$ for every pair of rows black in that column. Adding a cell to a column with $col[c]$ previous black cells creates exactly $col[c]$ new such row pairs.

Fourth, the maintained value of $P$ is exact because only pairs involving the updated row can change. If its size changes from $x$ to $x+1$, exactly the rows with size at least $x+1$ increase their pair minimum by $1$, which is exactly $ge[x+1]$ before the update.

Thus after every query, $D$ is exactly $\sum_{i<j}(\min(|S_i|,|S_j|)-|S_i\cap S_j|)$, and printing YES iff $D=0$ is correct.

Edge cases. Empty rows are harmless because they are subsets of everything. The first black cell always keeps $D=0$. The statement guarantees no cell is inserted twice, so column counts are enough; we never need a grid.

Complexity. Each query is $O(1)$. Each test case uses $O(n)$ memory. Over all tests, the complexity is $O(\sum(n+q))$.

Research checked: the official Codeforces problem/editorial page https://codeforces.com/blog/entry/151515, accepted-submission status https://codeforces.com/problemset/status/2201/problem/F1, and Luogu writeups https://www.luogu.com/article/fbtt01bd and https://www.luogu.com.cn/article/sxr8azbm.