CF2245D2.Construct an Array (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $n \le 2 \cdot 10^5$ and $0 \le m \le \min(10^6,\frac{n(n+1)}{2})$.

You are given two integers $n$ and $m$. You need to construct an integer array $a$ of length $n$ that satisfies $m$ restrictions. Each restriction can be represented by a tuple $(o,i,j)$ such that $o \in {1,2}$ and $1 \le i \le j \le n$:

• If $o=1$, the sum $a_i+a_j$ must be non-negative.
• If $o=2$, the sum $a_i+a_j$ must be negative.

这是该问题的困难版本。两个版本的区别在于，在本版本中，$n \le 2 \cdot 10^5$ 且 $0 \le m \le \min(10^6,\frac{n(n+1)}{2})$。

给定两个整数 $n$ 和 $m$。你需要构造一个长度为 $n$ 的整数数组 $a$，使其满足 $m$ 个限制条件。每个限制条件可表示为一个三元组 $(o,i,j)$，其中 $o \in \{1,2\}$ 且 $1 \le i \le j \le n$：

• 若 $o=1$，则和 $a_i+a_j$ 必须非负；
• 若 $o=2$，则和 $a_i+a_j$ 必须为负。

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

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le \color{red}{2 \cdot 10^5}$, $0 \le m \color{red}{\le} \min(10^6, \frac{n(n+1)}{2})$), representing the length of the array $a$ you need to construct and the number of restrictions, respectively.

Each of the next $m$ lines contains three integers $o$, $i$, and $j$ ($o \in {1,2}$, $1 \le i \le j \le n$), representing a restriction. It is guaranteed that each pair of integers $i$ and $j$ such that $1 \le i \le j \le n$ occurs in at most one restriction.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le \color{red}{2 \cdot 10^5}$，$0 \le m \color{red}{\le} \min(10^6, \frac{n(n+1)}{2})$），分别表示你需要构造的数组 $a$ 的长度以及限制条件的数量。

接下来的 $m$ 行中，每行包含三个整数 $o$、$i$ 和 $j$（$o \in \{1,2\}$，$1 \le i \le j \le n$），表示一条限制条件。保证对于任意满足 $1 \le i \le j \le n$ 的整数对 $(i,j)$，至多出现在一条限制条件中。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

保证所有测试用例的 $m$ 之和不超过 $10^6$。

For each test case, if no such array $a$ exists, output "NO".

Otherwise, first output "YES" on a single line. Then output $n$ integers $a_1,a_2,\ldots,a_n$ ($|a_i| \le 10^9$), representing the array $a$ you constructed. It can be proven that under the problem constraints, if such an array exists, there exists one where all elements in the array do not exceed $10^9$ in absolute value.

If there exist multiple arrays satisfying the requirement, you may output any of them.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，若不存在满足条件的数组 $a$，则输出 "NO"。

否则，首先在单独一行输出 "YES"；然后在下一行输出 $n$ 个整数 $a_1,a_2,\ldots,a_n$（满足 $|a_i| \le 10^9$），表示你构造出的数组 $a$。可以证明：在本题约束条件下，若满足条件的数组存在，则必存在一个所有元素绝对值均不超过 $10^9$ 的解。

若存在多个满足条件的数组，你可以输出其中任意一个。

你可使用任意大小写形式输出答案（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答）。

In the first test case, the only restriction is that $a_1+a_1$ is non-negative, implying that $a_1$ is non-negative. Thus, $a_1$ can be any non-negative integer.

In the second test case, the only restriction is that $a_1+a_1$ is negative, implying that $a_1$ is negative. Thus, $a_1$ can be any negative integer.

In the fourth test case, the first and second restrictions imply that both $a_1$ and $a_2$ are non-negative. However, the third restriction forces $a_1+a_2$ to be negative, which leads to a contradiction.

In the ninth test case, there are no restrictions. Any integer array $a$ is valid.

In the tenth test case, $[6,-6,4,-4,2,-2,0]$ is a valid solution. Note that $[7,-6,5,-4, 3, -2,1]$ is also a valid solution.

在第一个测试用例中，唯一的限制条件是 $a_1+a_1$ 非负，这意味着 $a_1$ 非负。因此，$a_1$ 可以是任意非负整数。

在第二个测试用例中，唯一的限制条件是 $a_1+a_1$ 为负数，这意味着 $a_1$ 为负数。因此，$a_1$ 可以是任意负整数。

在第四个测试用例中，前两个限制条件表明 $a_1$ 和 $a_2$ 均为非负数；然而，第三个限制条件要求 $a_1+a_2$ 为负数，这导致矛盾。

在第九个测试用例中，没有任何限制条件。任意整数数组 $a$ 均有效。

在第十个测试用例中，$[6,-6,4,-4,2,-2,0]$ 是一个有效解。注意，$[7,-6,5,-4,3,-2,1]$ 同样是一个有效解。