← 返回题目列表

Codeforces · 2201/F2

F2. 单调单色矩阵(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$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 \color{red}{2\,000\,000}$$$, $$$1 \le q \le \min(n^2,\color{red}{2\,000\,000})$$$)。

$$$q$$$ 以下行中的每一行都包含两个整数 $$$r_i$$$,$$$c_i$$$ 表示第 $$$i$$$ 查询($$$1 \le r_i,c_i \le n$$$)。

对于每个查询,保证单元格 $$$(r,c)$$$ 的颜色在查询之前为白色。

保证所有测试用例的$$$n$$$总和不超过$$$\color{red}{2\,000\,000}$$$。

保证所有测试用例的$$$q$$$总和不超过$$$\color{red}{2\,000\,000}$$$。

输出

对于每个查询,输出“是“或”NO”根据查询的答案在单独的行上。

任何情况下都可以输出答案。例如,字符串“是", "是“,和”是”也将被视为积极响应。

示例

输入
复制

2
3 9
2 2
3 3
2 3
3 1
3 2
1 1
1 2
2 1
1 3
5 17
2 1
4 5
4 1
3 3
3 1
3 5
1 3
1 5
1 1
5 3
5 5
5 1
1 4
5 2
5 4
1 2
2 5

输出
复制

YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO
YES
YES
YES

注意

在第一个测试用例中,$$$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$$$ 不是单调的查询中,以红色突出显示的四个方块表示违反上述条件的单元格。