题解：P14476 矩阵绘画

如果对合法染色方式计数，那么是容易的。考虑不相交的限制，提取出激活的 $a$ 的前缀 $\max$，对这些前缀 $\max$ 做 dp，此时就将矩阵划分成了一些区域，每个区域要么全选列要么全选行，这样是容易计数的，处理 $[1,i]$ 中所有后缀中 $b_j<a_i$ 的信息即可，再预处理一下每个行，列的 0 和 1 信息，可以 $\mathcal O(n^2)$ 的复杂度算。

问题在于重复计数。考虑一个重复算的区域，要么是前缀全选行，要么是前缀全选列（一个 $2\times 2$ 内部全为 $1$ 的区域，考虑两行均被行染色以及两行均被列染色）。$a_1=0$ 时压根不会数重，进而，猜测每个矩阵只会被至多两种方案算到。这样我们容斥：用总操作方案数，减去会被算到两次的矩阵个数，就是最终答案。

进而，只关心左上角 $x\times y$ 的矩阵内部，要求 $\max_{i\leq x}a_i\leq y,\max_{i\leq y}b_i\leq x$，并且全选行与全选列构成的 $01$ 矩阵完全相同。然后再乘上剩余部分的染色方案数即可，一个必要条件是 $a,b$ 单调不增，进而发现，这个区域只能取到 $x=b_1,y=a_1$。这里再做 dp 可以沿用对 $a$ 的前缀 $\max$ 计数的思路，但是要修改 $a_1$ 之后第一个前缀 $\max$ 的值。

时间复杂度 $\mathcal O(n^2)$。

代码咕咕咕，如有错误请指出。