寻找平均值大于或等于K的子数组数量。

Question

给定一个整数数组，找到平均值大于等于K的子数组数量。

约束条件：

1 <= N <= 10^5
-10^9 <= A[i] <= 10^9

我的解决方案：

如果A[i]是数组中第i个索引的前缀和，则

(A[j] - A[i]) / (j - i) >= K
(A[j] - A[i]) >= K * (j - i)
(A[j] - K * j) >= (A[i] - K * i) <- Let's call this expression e

所以表达式e告诉我，如果我将当前索引的运行总和与-K * current index一起哈希，那么我只需要搜索小于表达式e的元素数量。

在处理完ith索引后，我在哈希表中映射的内容是A [i] - K * i，其中A [i]是数组的运行总和

但我一直在努力寻找一个数据结构，它可以在常数时间或O(logN)时间内给出小于给定元素的元素数量。

我探索过的解决此问题的数据结构如下：

1. 线段树，但约束条件太高了，因为我们需要分配最大大小。
2. 多重集合 (C++) 并执行 upper_bound (二进制搜索)，这将给我迭代器，并且要获得小于X的元素，我可以找到upper_bound和begin()迭代器之间的差异，但此方法的运行时可能会达到O(N)，然后我的整体运行时间就变成了O(N^2)。

注意：考虑到C ++作为主要语言，我在问题中提到了C ++。

非常期待听到您的想法/建议。

- Ajay Kumar

Answer 1

你已经设置了 A[i] = A[i] - (K * i)，所以你需要找到所有的 i,j，使得

A[j] - A[i] >= 0, or
A[j] >= A[i]

假设 j>i，有效对数应该是总对数减去逆序对计数。这样你就不需要任何特殊的数据结构（一个数组就足够了），逆序对计数可以在O(NlogN)时间内完成。

- Abhinav Mathur

---

很棒的见解，Abhinav。我错过了以这种方式查看表达式。 如果我们可以使用表达式构建一个数组，并且在遍历时确保相对顺序得到保留。 因此，问题就简化为在构建的数组中找到逆序计数的数量。接受答案。谢谢Abhinav。 - Ajay Kumar

新的洞见被揭示。 - Ajay Kumar