2 个数组之间最佳分区中的最大总和对

问：

有 2 个数组。 和 N 轮输入 每一轮 I 我们都会得到输入（AI、BI） ai 将保存在列表 A 中 和 bi 将保存在列表 B 中 每一轮我们都会得到最优分区中最大对和的输出。 最优分区 = 对列表 （A[I]， B[j]），其中列表中的最大总和是所有对分区中的最小-最大总和

我找到了 o（N^2） 算法，但我需要 o（nlog（n））：

O（n^2）： （获得 n 对）

1. 按递增顺序对数组 A 进行排序 o（nlogn）
2. 按降序对数组 B 进行排序 o（nlogn）
3. 为 0 创建对 [A[i]， B[i]] <= i < n
4. 遍历所有货币对并返回最大总和。

每一轮我们再增加一对（AI、BI）：

1. 使用二进制在排序的 A 中找到 ai 的位置，在排序的 B 中找到 bi 的位置 搜索 O（logn）
2. 遍历所有新货币对，并返回最大总和。（o（n））

假设我们有 N 轮，算法将取 O（n^2） 我该如何优化它？