查询次数较多时，如何将大于k的数组范围内的元素替换为k？假设每个查询都以 lrk 形式给出；其中 [l...r] 是数组的范围。
问问题
358 次
1 回答
0
由于我的第一个答案创建了大量评论，我将把所有内容合并到新答案中。
我们将使用 Segment Tree 作为辅助数据结构，用于回答这个问题：范围 [l, r] 的最小值是多少。最初，所有分段树节点都将填充一些“无穷大”数字，在您的问题中可能是 201（因为根据您的评论，所有 K 都低于 200）。
一旦我们读取了输入数组（我们称之为 A），我们将处理查询：
对于每个查询 [L, R, K]，我们将更新我们的段树：尝试在范围 [L, R] 上设置新的最小 K。这可以通过使用延迟传播的 O(LogN) 来完成。这是一个很好的例子http://se7so.blogspot.com/2012/12/segment-trees-and-lazy-propagation.html
现在我们需要构建最终数组。我们正在遍历数组中的每个索引并将其替换为 A[i] = min(A[i], minimum_on_range(i, i))。这将需要 N * Log(N) 步骤
该方法的总复杂度为M * Log(N) + N * Log(N)
于 2015-07-12T14:09:21.403 回答