如何用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，並且我們只對最終數組感興趣，那麼這種方法仍然可以使用嗎？ –

回答