Set To Max (Hard Version) (Codeforces 1904D2)
Tags: Greedy, divide and conquer

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:   choose $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$.  let $$$x=\max(a_l,a_{l+1},\ldots,a_r)$$$.  for all $$$l \leq i \leq r$$$, set $$$a_i := x$$$. Determine if you can make array $$$a$$$ equal to array $$$b$$$.

Input: 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$$$.

Output: 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).

Note: 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.

Sample Inputs:
5
5
1 2 3 2 4
1 3 3 2 4
5
3 4 2 2 4
3 4 3 4 4
5
3 2 1 1 1
3 3 3 2 2
2
1 1
1 2
3
1 1 2
2 1 2

Sample Outputs:
YES
NO
YES
NO
NO

Solution (Python):
from sys import stdin
input = lambda : stdin.buffer.readline().decode().strip()
from collections import deque
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def solve(order):
        dq = deque()
        for i in order:
            while dq and dq[-1] <= a[i]:
                dq.pop()
            while dq and dq[0] > b[i]:
                dq.popleft()
            dq.append(a[i])
            if dq[0] == b[i]:
                a[i] = b[i]
    solve(range(n))
    solve(reversed(range(n)))
    print('YES' if a == b else 'NO')

Solution (Python):
from sys import stdin
input = lambda : stdin.buffer.readline().decode().strip()
from collections import deque
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def solve(order):
        dq = deque()
        for i in order:
            while dq and dq[-1] <= a[i]:
                dq.pop()
            while dq and dq[0] > b[i]:
                dq.popleft()
            dq.append(a[i])
            if dq[0] == b[i]:
                a[i] = b[i]
    solve(range(n))
    solve(reversed(range(n)))
    print('YES' if a == b else 'NO')

Solution (Python):
from sys import stdin
input = lambda : stdin.buffer.readline().decode().strip()
from collections import deque
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def solve(order):
        dq = deque()
        for i in order:
            while dq and dq[-1] <= a[i]:
                dq.pop()
            while dq and dq[0] > b[i]:
                dq.popleft()
            dq.append(a[i])
            if dq[0] == b[i]:
                a[i] = b[i]
    solve(range(n))
    solve(reversed(range(n)))
    print('YES' if a == b else 'NO')