algorithm - 查找 min(max(A[L], A[L+1],...,A[R]), min(B[L], B[L+1],..., B[R] 的有效方法))

Question

给定 2 个数组 A[N] 和 B[N]。对于每个 0 <= L < N <= 5e5，找到最大值

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

对于 L <= R <= N。

ans[L] 是 L 的答案。
例如，
N = 3
A[3] = {3, 2, 1}
B[3] = {3, 2, 3}
所以，答案是
ans[0] = 3
答[1] = 2
答案[2] = 1

很明显，蛮力可以跑得很快。
然后，我尝试使用稀疏表、线段树或二叉索引树(并且我们不需要更新任何内容，所以我选择稀疏表)。但是对于每个 L，我们不知道 R，所以我需要运行到数组的末尾，这与暴力破解没有什么不同。

有没有有效的算法或数据结构来解决这个问题？

P/s:抱歉我的英语不好。

Answer 1

使用稀疏表A是单调递增的，B是单调递减的，所以我们需要找到交叉点以从它们的最小值中得到最大值...

未经测试的伪 python 代码

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?