我必须设计一个数据结构,使我有一个大小为 N 的数组 A,即 A[1],A[1],A[2],...A[n]
.我必须处理两种类型的查询(总共有 M 个查询):
- 在数组A中从i到j的范围内加1
- 在数组A中找到第K小的元素
给定1<=N,M<=200000.
首先,我想到了通过对每个桶进行排序来进行平方根分解,但无法更新属于不同桶的部分范围。你能建议如何去做吗?
我想要一些 O(N*Log(N))
或 O(N*SQRT(N))
复杂性。
最佳答案
这看起来像是一个相当典型的竞争性编程问题。我想我有一个解决方案,虽然它有点难看 - 也许你可以改进它。
我们将在解决方案的核心使用平方根分解(如果您不熟悉此方法,请参阅 link)。对于每个 block ,我们将保留:原样的元素值(我们将其命名为 A
),整个 block 的添加数(一个整数,我们将其命名为 extra
) 和 IND
- 按值排序的 block 索引数组(例如,如果 block 元素为 [4, 2, 5],则索引数组将为 [1, 0, 2])。现在让我们来看看这如何让我们解决问题以及复杂性是什么。
初始化
对于每个 sqrt(N)
block ,我们必须对其进行排序(sqrt(N) * log(sqrt(N))
每个 block ),以获得初始索引数组,导致 sqrt(N) * sqrt(N) * log(sqrt(N)) = N * log(N)
初始化复杂度。
将 1 添加到范围 (l, r)
就像进行常规的 sqrt 分解更新一样进行。对于完全在范围内的每个 block ,我们将增加 extra
计数器。一个重要的观察是元素的相对顺序没有改变,所以我们在这里的工作已经完成。对于部分在更新范围内的 block ,我们执行以下操作:通过将适当的元素递增 1 来更新 A
,通过排序重新生成 IND
数组。请注意,最多有两个部分更新 block 。 O(1)
中“完整” block 更新的总复杂度,其中有 sqrt(N)
。部分更新是 sqrt(N) * log(sqrt(N)) = sqrt(N) * log(N)
,总更新复杂度为 sqrt(N) * log(N )
。有 M 个查询,所以在最坏的情况下,这些更新将贡献 M * sqrt(N) * log(N)
。
找到第K小的元素
让我们弄清楚如何找到数组中小于某个值 L
的元素数。为此,对于每个 block ,我们将对 IND
数组进行二进制搜索。当我们从该数组中获得一些索引 idx
时,要使用的实际值是 A[idx] + extra
,其中 A
和 extra
来自那个 block 。此过程允许我们获取每个 block 内大于 L
的元素数。之后,我们只需对每个 block 的结果求和。要处理一个 block ,我们必须花费 log(sqrt(N)) = log(N)
进行二分查找,并且有 sqrt(N)
个 block ,导致 sqrt(N) * log(N)
复杂度。
为了得到第 K 个最小的元素,我们将对可能的答案进行另一个二进制搜索(竞争编程中的常用技术),我们将在最小和最大可能答案(例如最小元素和最大元素)之间进行二进制搜索加上 M
)。我们将此范围表示为 C
。在每一步中,我们都会检查有多少元素小于我们当前的猜测,当我们找到第 K 个最小的元素时,我们就会得到答案。如果您需要对此步骤进行更多详细说明,请告诉我。
最终复杂度变为log(C) * sqrt(N) * log(N)
,可以有M个查询,使得M * log(C) * sqrt( N) * 日志(N)
。如果初始数组全为零或值在 0
到 M
范围内,这将是 M * log(M) * sqrt(N) * log(N )
。或者您可以选择将 C
视为常量(这不太正确)。
我很确定其中一个 log
可以被削掉,但这留给读者作为练习:)
关于algorithm - 如何创建具有此类属性的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54566530/