给定的数组是前 n 个整数的排列。给定两个范围 [l1,r1] &[l2,r2] 。我们必须找到，对于第一个范围内的每个元素 a[i]；第二个范围内大于该范围的元素数。（两个范围的长度相等）
我首先对两个范围进行了排序。然后迭代第一个范围内的每个元素，计算大于第二个范围内的元素数。记下前一个计数。所以我的迭代只是 O(l) [l=每个范围的长度]
我的总体时间复杂度是 O(l*log(l))..但是由于我正在为许多范围查询计算这个，所以它需要很多时间。
我认为这个问题类似于计算数组中的反转次数。但由于涉及两个范围和许多查询，我无法解决。我不确定，但我认为一些 fenwick 树结构可能会有所帮助。有人可以提出一些重要的建议吗？