Efficient way to find min(max(A[L], A[L+1],...,A[R]), min(B[L], B[L+1],…, B[R]))

Question

Given 2 array A[N] and B[N]. For each 0 <= L < N <= 5e5, find the maximum value of

min(max(A[L], A[L+1],...,A[R]), min(B[L], B[L+1],…, B[R])) 

for L <= R <= N.

ans[L] is the answer for L.
For example,
N = 3
A[3] = {3, 2, 1}
B[3] = {3, 2, 3}
So, the answer is
ans[0] = 3
ans[1] = 2
ans[2] = 1

It is clear that brute-forces can run fast.
Then, I tried using Sparse table, Segment Tree or Binary Indexed Tree (and we don't need to update anything, so I choose Sparse Table). But for each L, we don't know R, so I need to run to the end of the array, and this doesn't different from brute-forces .

Is there any efficient algorithm or data structures for this problem??

P/s: Sorry for my bad English.

Answer 1

Using Sparse table A is monotone increasing, B is monotone decreasing, so we need to find the crossing point to get the max out of their min ...

pseudo python code untested

stA = SparseTable(A);
stB = SparseTable(B);

for (i in range(len(A))
  r = len(B)
  l = i

  a = stA.max(l,r)
  b = stB.min(l,r)

  # binary search for crossing point
  while (l != r)
    m = l + (r-l)//2  # integer division 
    a = stA.max(l,m)
    b = stB.min(l,m)
    if (b > a)
      l = m + 1
    else
      r = m

  ans[i] = min(a,b) # might be off-by-one m?