CF1904D2 Set To Max (Hard Version)

这是该问题的困难版本。两种版本的区别仅在于 $n$ 的限制和时间限制。只有在所有版本的问题都被解决后，你才能进行 hack。 给定两个长度为 $n$ 的数组 $a$ 和 $b$。 你可以进行如下操作若干次（也可以一次都不做）： 1. 选择 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$。 2. 令 $x = \max(a_l, a_{l+1}, \ldots, a_r)$。 3. 对所有 $l \leq i \leq r$，令 $a_i := x$。 请判断你是否可以通过若干次操作将数组 $a$ 变为数组 $b$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示数组 $a$ 的元素。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq n$），表示数组 $b$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果可以通过若干次操作将 $a$ 变为 $b$，输出 "YES"（不含引号）；否则输出 "NO"（不含引号）。 你可以以任意大小写输出 "YES" 和 "NO"（例如 "yES"、"yes" 和 "Yes" 都会被识别为肯定回答）。

在第一个测试用例中，我们可以通过一次操作 $(l, r) = (2, 3)$ 得到数组 $b$。 在第二个测试用例中，可以证明无论进行多少次操作都无法得到数组 $b$。 在第三个测试用例中，我们可以先进行一次操作 $(l, r) = (2, 5)$，再进行一次操作 $(l, r) = (1, 3)$，从而得到数组 $b$。 在第四个和第五个测试用例中，可以证明无论进行多少次操作都无法得到数组 $b$。 由 ChatGPT 4.1 翻译