CF2201F2.Monotone Monochrome Matrices (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $n$ and $q$ are very large. You can hack only if you solved all versions of this problem.

A monochrome matrix of size $n \times n$ is a matrix of $n$ rows and $n$ columns, where each cell is colored either black or white. Let the color of cell $(r,c)$ in a monochrome matrix $C$ be denoted as $C[r,c]$.

Let's call such a matrix $C$ monotone if it satisfies the following condition:

• There exist no two rows $1 \le i \lt j \le n$ and two columns $1 \le k \lt l \le n$ that satisfy the following three conditions:
  • $C[i,k]=C[j,l]$;
  • $C[j,k]=C[i,l]$;
  • $C[i,k] \neq C[j,k]$.

There is a monochrome matrix $M$ of size $n \times n$, where all cells are initially white. Please solve $q$ queries of the following kind:

• $r\;c$: Change the color of the cell $(r,c)$ in $M$ to black. Then, determine if $M$ is monotone or not.

For each query, it is guaranteed that the color of the cell $(r,c)$ was white before the query.

Do note that the updates are persistent. In other words, the change in color from one query affects the later queries as well.

这是该问题的困难版本。两个版本的区别在于，本版本中 $n$ 和 $q$ 的约束非常大。仅当您已解决该问题的所有版本时，才可进行 Hack。

一个 $n \times n$ 的单色矩阵是指一个具有 $n$ 行和 $n$ 列的矩阵，其中每个格子被染成黑色或白色。记单色矩阵 $C$ 中位置 $(r,c)$ 处格子的颜色为 $C[r,c]$。

若矩阵 $C$ 满足如下条件，则称其为单调矩阵（monotone）：

• 不存在两行 $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]$。

给定一个初始全为白色的 $n \times n$ 单色矩阵 $M$。请处理 $q$ 个如下类型的查询：

• $r\;c$：将矩阵 $M$ 中位置 $(r,c)$ 处的格子染成黑色；随后判断当前 $M$ 是否为单调矩阵。

对于每个查询，保证在执行该查询前，格子 $(r,c)$ 的颜色为白色。

请注意，所有更新是持久化的。换言之，某次查询所引起的颜色变化会影响后续所有查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \le n \le \color{red}{2\,000\,000}$, $1 \le q \le \min(n^2,\color{red}{2\,000\,000})$).

Each of the $q$ following lines contains two integers $r_i$, $c_i$ denoting the $i$-th query ($1 \le r_i,c_i \le n$).

For each query, it is guaranteed that the color of the cell $(r,c)$ was white before the query.

It is guaranteed that the sum of $n$ over all test cases does not exceed $\color{red}{2\,000\,000}$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $\color{red}{2\,000\,000}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$。

For each query, output "YES" or "NO" on a separate line based on the answer of the query.

You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

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

您可以以任意大小写形式输出答案。例如，字符串 “yEs”、“yes” 和 “Yes” 也会被识别为肯定回答。

In the first test case, $M$ has size $3 \times 3$. The states of $M$ after each query are as shown below.

\\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}

On queries where $M$ is not monotonic, the four squares highlighted in red denote cells that violate the condition stated above.

在第一个测试用例中，矩阵 $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$ 不满足单调性条件的查询，图中以红色高亮显示的四个方格表示违反上述条件的单元格。