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

EN

# 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))