arrays - 给定两个无序列表，查询 A[i] > a 和 B[i] > b 的元素数

Question

考虑两个数组 A 和 B。数组 A 中索引为 i 的元素与数组 B 中索引为 i 的元素相关联。我们可以将它们视为一对。我们有一些形式为 (a, b) 的查询 q。我们需要找到 A[i] > a 和 B[i] > b 的所有此类元素的计数。

Constraints - 
n (size of array) <= 10^5
q (count of queries) <= 10^5
 

Example - 
A = [1,  3, 6, 7, 2]
B = [10, 7, 2, 6, 4]
q = [(2, 6), (3, 9), (0, 1)]

Output - 
[1, 0, 5]

解释-
对于查询 (2, 6)，只有一个实体使得 A[i] > 2 和 B[i] > 6。对于第一个条件 A[i] > 2，我们有三个候选 - 3, 6, 7 但基于在第二个条件 B[i] > 6 对于这些候选者，只有一个答案是第一个数组 (3, 7) 中值为 3 的候选者。
我尝试了线性搜索的蛮力方法，但这导致了 TLE。

Answer 1

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

# Order statistic treap

import random

class Treap:
  def __init__(self, val=None):
    self.val = val
    self.size = 1
    self.key = random.random()
    self.left = None
    self.right = None

  def __repr__(self):
    return str({"val": self.val, "size": self.size, "key": self.key, "left": self.left, "right": self.right})

def size(t):
  return t.size if t else 0

def update(t):
  if t:
    t.size = 1 + size(t.left) + size(t.right)
  return t

def insert(t, node):
  if not t:
    return node

  # t above
  if node.key > t.key:
    if node.val > t.val:
      t.right = insert(t.right, node)
      return update(t)
    else:
      t.left = insert(t.left, node)
      return update(t)
  # node above
  else:
    if node.val > t.val:
      node.left = insert(node.left, t)
      return update(node)
    else:
      node.right = insert(node.right, t)
      return update(node)

def query(t, val):
  if not t:
    return 0

  if val < t.val:
    return 1 + size(t.right) + query(t.left, val)
  else:
    return query(t.right, val)


def merge_queries(lst, Q):
  result = [None] * (len(lst) + len(Q))

  i = 0
  j = 0

  for k in range(len(result)):
    if i < len(lst) and (j == len(Q) or lst[i][0] <= Q[j][0]):
      result[k] = lst[i]
      i += 1
    else:
      result[k] = Q[j]
      j += 1

  return result


def f(A, B, Q):
  sorted_zip = sorted(zip(A, B))
  sorted_queries = sorted([(a, b, i) for i, (a, b) in enumerate(Q)])
  merged = merge_queries(sorted_zip, sorted_queries)

  result = [None] * len(Q)
  tree = None

  for tpl in reversed(merged):
    if len(tpl) == 3:
      result[tpl[2]] = query(tree, tpl[1])
    else:
      tree = insert(tree, Treap(tpl[1]))

  return result


A = [1,  3, 6, 7, 2]
B = [10, 7, 2, 6, 4]
Q = [(2, 6), (3, 9), (0, 1)]

print(f(A, B, Q))