如何用k替换小于k的范围元素？

-4

当查询数很高时，如何将大于k的数组范围内的元素替换为k？假设每个查询都是由形式l r k给出的;其中[l ... r]是阵列的范围。如何用k替换小于k的范围元素？

你能告诉你做的事这个？ – ameyCU

我已经使用了朴素的方法来进行comap和k替换。由于查询次数非常多，因此复杂度为m * n。我想要一个高效的算法来做到这一点。 –

我想在所有查询实施后更新数组 –

由于我的第一个答案创建了大量的评论意见，我将在新的答案中结合所有内容。

我们将使用Segment Tree作为辅助数据结构，它将用于回答这个问题：范围[l，r]上的最小值是多少。最初，所有分段树节点都会填充一些“Infinity”数字，这可能是您的问题中的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 *日志（n）步

这种做法的总的复杂性是M *日志（N）+ N *日志（N）

2015-07-12 14:09:21 serhiyb

这是一个很好的解释，但你能解释我怎样才能“设置新的最小K在范围[L，R]”。如果数组A的所有元素初始为201，并且我们只对最终数组感兴趣，那么这种方法仍然可以使用吗？ –

回答