c++ - 找出平均值大于或等于 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 * 当前索引，那么我需要搜索的是元素少表达式 e.

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

但我一直在努力寻找一种数据结构，它可以在常数时间内或可能是 O(logN) 时间内为我提供少于给定元素的元素数。

我为解决这个问题而探索的数据结构-

1. 线段树，但线段树的约束太高，因为我们需要分配最大尺寸。
2. Multi-sets (C++) 并执行 upper_bound(二进制搜索)这会给我迭代器，并获取小于 X 的元素我可以找到不同之处在 upper_bound 和 begin() 迭代器之间，但它的运行时间可能会达到 O(N) 然后我的总运行时间会达到 O(N^ 2).

注意:无论我在问题中提到什么，都将 C++ 视为主要语言，因为我是用 C++ 解决问题的。

很想听听您的想法/建议。

Answer 1

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

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

假设j>i，有效对的数量应该是总对数减去inversion count。 .这样您就不需要任何特殊的数据结构(一个数组就足够了)，并且可以在 O(NlogN) 中完成反转计数计算。