列表中二维对（x，y）的倒数计数

Question

这个问题就像普通的计数反转问题一样，但现在输入的不是单个数字的列表，而是（x，y）对的列表

对于对的列表[（x1，y1），（x2，y2），（x3，y3），…，（xn，yn）]，对（i，j）是反转iffi < j和xi>xj，yi>yj。可以用O（nlognlogn）写算法吗？我尝试了几种方法，但在合并步骤中，列表右半部分的每个元素都必须与左半部分的所有元素进行比较，导致时间复杂度为n平方

Answer 1

根据x坐标将列表分成两部分left和right。然后，比较两半的最低点（基于它们的y坐标）。有两种情况：

1. 左点低于右点，则左点对其右侧的所有点具有xi<xj和yi<yj
2. 右点低于左点，因此yi>yj条件对其左侧的任何点都适用。
   根据这两种情况更新答案后，您可以删除这两点中的一点并继续处理剩余的排序列表（通过递归求解left和right）。这应该在O(nlog^2n)中起作用