CF1904D2 Set To Max (Hard Version)

This is the hard version of the problem. The only differences between the two versions of this problem are the constraints on $ n $ and the time limit. You can make hacks only if all versions of the problem are solved. You are given two arrays $ a $ and $ b $ of length $ n $ . You can perform the following operation some (possibly zero) times: 1. choose $ l $ and $ r $ such that $ 1 \leq l \leq r \leq n $ . 2. let $ x=\max(a_l,a_{l+1},\ldots,a_r) $ . 3. for all $ l \leq i \leq r $ , set $ a_i := x $ . Determine if you can make array $ a $ equal to array $ b $ .

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the arrays. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of array $ a $ . The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le n $ ) — the elements of array $ b $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output "YES" (without quotes) if you can make $ a $ into $ b $ using any number of operations, and "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

In the first test case, we can achieve array $ b $ by applying a single operation: $ (l,r)=(2,3) $ . In the second test case, it can be shown we cannot achieve array $ b $ in any amount of operations. In the third test case, we can achieve array $ b $ by applying two operations: $ (l,r)=(2,5) $ . followed by $ (l,r)=(1,3) $ . In the fourth and fifth test cases, it can be shown we cannot achieve array $ b $ in any amount of operations.