这是问题的中等版本。版本之间的区别在于,在这个版本中,$$$n$$$ 和 $$$q$$$ 的约束更大。只有解决了该问题的所有版本,您才能破解。
A 单色矩阵 大小为 $$$n \times n$$$ 是一个由 $$$n$$$ 行和 $$$n$$$ 列组成的矩阵,其中每个单元格的颜色为黑色或白色。设单色矩阵$$$C$$$中单元格$$$(r,c)$$$的颜色表示为$$$C[r,c]$$$。
我们将这样的矩阵称为 $$$C$$$ 单调 如果满足以下条件:
- 不存在满足以下三个条件的两行 $$$1 \le i \lt j \le n$$$ 和两列 $$$1 \le k \lt l \le n$$$:
- $$$C[i,k]=C[j,l]$$$;
- $$$C[j,k]=C[i,l]$$$;
- $$$C[i,k] \neq C[j,k]$$$。
有一个单色矩阵 $$$M$$$,大小为 $$$n \times n$$$,其中所有单元格最初都是白色的。请解决以下类型的 $$$q$$$ 查询:
- $$$r\;c$$$:将$$$M$$$中单元格$$$(r,c)$$$的颜色更改为 黑色。然后,确定 $$$M$$$ 是否单调。
对于每个查询,保证单元格 $$$(r,c)$$$ 的颜色在查询之前为白色。
请注意,更新是持久的。换句话说,一个查询的颜色变化也会影响后面的查询。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le \min(n^2,200\,000)$$$)。
$$$q$$$ 以下行中的每一行都包含两个整数 $$$r_i$$$,$$$c_i$$$ 表示第 $$$i$$$ 查询($$$1 \le r_i,c_i \le n$$$)。
对于每个查询,保证单元格 $$$(r,c)$$$ 的颜色在查询之前为白色。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$200\,000$$$。
输出
对于每个查询,输出“是“或”NO”根据查询的答案在单独的行上。
任何情况下都可以输出答案。例如,字符串“是", "是“,和”是”也将被视为积极响应。
示例
输入复制
23 92 23 32 33 13 21 11 22 11 35 172 14 54 13 33 13 51 31 51 15 35 55 11 45 25 41 22 5
输出复制
YESNOYESNOYESNONOYESYESYESNOYESNONOYESNONOYESNONOYESYESNOYESYESYES
注意
在第一个测试用例中,$$$M$$$ 的大小为 $$$3 \times 3$$$。每次查询后$$$M$$$的状态如下所示。
$$\quad\, \begin{bmatrix} \square & \square & \square\\ \square & \blacksquare & \square\\ \square & \square & \square \end{bmatrix} \to \begin{bmatrix} \square & \square & \square\\ \square & \color{red}{\blacksquare} & \color{red}{\square}\\ \square & \color{red}{\square} & \color{red}{\blacksquare} \end{bmatrix} \to \begin{bmatrix} \square & \square & \square\\ \square & \blacksquare & \blacksquare\\ \square & \square & \blacksquare \end{bmatrix} \\\to \begin{bmatrix} \square & \square & \square\\ \color{red}{\square} & \color{red}{\blacksquare} & \blacksquare\\ \color{red}{\blacksquare} & \color{red}{\square} & \blacksquare \end{bmatrix} \to \begin{bmatrix} \square & \square & \square\\ \square & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \to \begin{bmatrix} \color{red}{\blacksquare} & \color{red}{\square} & \square\\ \color{red}{\square} & \color{red}{\blacksquare} & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \\\to \begin{bmatrix} \color{red}{\blacksquare} & \blacksquare & \color{red}{\square}\\ \color{red}{\square} & \blacksquare & \color{red}{\blacksquare}\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \to \begin{bmatrix} \blacksquare & \blacksquare & \square\\ \blacksquare & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix} \to \begin{bmatrix} \blacksquare & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare\\ \blacksquare & \blacksquare & \blacksquare \end{bmatrix}$$
在 $$$M$$$ 不是单调的查询中,以红色突出显示的四个方块表示违反上述条件的单元格。