如何将小于k的范围内的元素替换为k？
How to replace the elements of a range less than k with k?
查询次数多时，如何将大于k的数组范围内的元素替换为k？
假设每个查询都以 l r k 的形式给出；其中 [l...r] 是数组的范围。
由于我的第一个回答产生了大量的评论，我将把所有内容合并到新的回答中。
我们将使用线段树作为辅助数据结构来回答这个问题：范围 [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 * Log(N) 步
该方法的总复杂度为 M * Log(N) + N * Log(N)
查询次数多时，如何将大于k的数组范围内的元素替换为k？ 假设每个查询都以 l r k 的形式给出；其中 [l...r] 是数组的范围。
由于我的第一个回答产生了大量的评论，我将把所有内容合并到新的回答中。
我们将使用线段树作为辅助数据结构来回答这个问题：范围 [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 * Log(N) 步
该方法的总复杂度为 M * Log(N) + N * Log(N)