当查询次数很高时，如何替换大于k × k的数组范围内的元素?假设每个查询都由l r k的形式给出;在[l…R]是数组的范围
由于我的第一个答案引起了大量的评论，我将把所有的东西合并到新的答案中。
我们将使用段树作为辅助数据结构，它将用于回答这个问题:在范围[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)