Monotone Monochrome Matrices (Easy Version)

Research note: I checked the Codeforces statement, the official tutorial page whose G1/F1/F2 section is currently just the placeholder, public accepted-status pages such as F1 status, and a Codeforces comment on that tutorial page pointing at the Young-diagram/count-histogram approach. The proof below is derived from the supplied statement; no source text is copied.

The forbidden configuration is just a checkerboard:

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

For row $i$, let $S_i$ be the set of columns where row $i$ is black. For two rows $i,j$, a bad checkerboard exists exactly when the two sets are incomparable: there is some column in $S_i\setminus S_j$ and some column in $S_j\setminus S_i$. The order of those two columns does not save you; whichever is smaller becomes $k$, the other becomes $l$, and boom, checkerboard. Conversely, any checkerboard gives one column from each difference. Therefore:

$$M\text{ is monotone} \iff S_1,S_2,\ldots,S_n\text{ are pairwise comparable by inclusion}.$$

This is the first big trap: the row indices do not need to be monotone. We are allowed to conceptually reorder rows and columns. The property is about nested sets, not about row $1$ being above row $2$ in some nice visual way.

Now sort row counts in nonincreasing order:

$$\lambda_1\ge \lambda_2\ge \cdots \ge \lambda_n.$$

If the row sets are nested, these counts describe a Young diagram. Its column heights are the conjugate partition:

$$g_k = \#\{i : \lambda_i\ge k\},\qquad 1\le k\le n.$$

So the actual multiset of column black counts must equal the multiset $\{g_1,g_2,\ldots,g_n\}$, including zeroes. That last bit matters; ignoring empty columns is how bugs sneak in wearing a fake mustache.

The converse is also true. Suppose the actual column-count multiset equals the conjugate of the sorted row-count multiset. Let $g_1$ be the number of nonempty rows. Since no empty row contains black cells, any column with height $g_1$ must be black in every nonempty row. Such a column exists by the multiset equality. Remove it and subtract $1$ from every nonempty row count. The remaining expected column-height multiset is just the old conjugate with $g_1$ removed. Repeat. Each removed column is present in exactly the rows that are still active, so the rows are forced into nested sets. Thus the count criterion is equivalent to monotonicity.

So we maintain this criterion dynamically.

Let $C_h$ be the number of actual columns with exactly $h$ black cells.

Let $A_k$ be the number of rows with at least $k$ black cells:

$$A_k=\#\{r: \text{rowCount}[r]\ge k\}.$$

The expected conjugate-column multiset contains one value $A_k$ for every $k=1,2,\ldots,n$. Define

$$E_h = \#\{k : A_k=h\}.$$

The matrix is monotone iff

$$C_h=E_h\quad\text{for every }0\le h\le n.$$

Maintain $\Delta_h=C_h-E_h$ and a counter bad = number of $h$ with $\Delta_h\ne 0$. Answer is YES iff bad == 0.

Initially all cells are white. Then $C_0=n$, and since $A_k=0$ for all $k$, also $E_0=n$. All differences are zero.

For a query adding cell $(r,c)$:

• Let $a$ be the old black count of row $r$.
• Let $b$ be the old black count of column $c$.
• The actual column histogram changes as $C_b--$ and $C_{b+1}++$.
• Only one threshold value $A_k$ changes: $k=a+1$. Before the row update, row $r$ is not counted in $A_{a+1}$; after the update, it is. Let

$$x=A_{a+1}=\#\{\text{rows with count}\ge a+1\}\quad\text{before the update}.$$

Then the expected histogram changes as $E_x--$ and $E_{x+1}++$.

Since $\Delta=C-E$, these four histogram moves become four point updates to $\Delta$:

$$\Delta_b--, \quad \Delta_{b+1}++, \quad \Delta_x++, \quad \Delta_{x+1}--.$$

We get $x$ using a Fenwick tree over row-count frequencies. The Fenwick tree supports updating one row count and querying how many rows have count at least some threshold.

Complexity per query is $O(\log n)$, with $O(n)$ memory. Across all test cases this is easily fine for $\sum q\le 200000$ and $\sum n\le 25000$.