algorithm - 给定两个未排序的数组，找到 A[i] > X 和 B[i] > Y 的对数

Question

我们有两个未排序的数组。我们必须找到对的数量，使得对于每一对 A[i] > X 和 B[i] > Y。我们将不得不处理 100 万个这样的查询，其中每个查询将给出不同的 X 和 Y。数组的长度也将达到100万。

约束:

1 <=A[i],B[i],X,Y <=10^9 1<= A.size, B.size, 查询数<= 10^6

例如:

     A = [7,2,10,15,12,9]
     B = [10,8,5,3,4,7]

查询:

      X Y   o/p
      9 3    2  (As we have 2 pairs which satisfy above condition (10,5), (12,4))
      6 4    3  (As we have 3 pairs which satisfy above condition (7,10), (10,5), (9,7))

鉴于我们有 100 万个此类查询，是否有比暴力破解更好的方法？

Answer 1

如果离线提供查询，则不需要四叉树，我们可以在 O(n log n) 中解决这个问题。将所有查询对和数组对插入一个列表，按 X 或 a 排序(如果 X 等于 a，将查询对放在数组对之后)。按降序(a 或 X)处理列表中的对。如果是数组对，则将其插入到按b排序的顺序统计树中。如果是查询，在树中查找具有 b > Y 的树节点(这些是数组对)的计数(我们已经知道树中的所有对都具有 a > X)。