对N个元素的数组A执行Q查询。在每个查询中，选择索引I，然后执行以下操作。
for j = I + 1 to N:
if A[j] < A[I]:
A[j] = 0
处理完Q查询后，数组A的外观如何。
1 <= N,Q <= 10^5
1 <= A <= 10^9
Test Case :
5 2 (N Q)
4 3 4 3 2
3 2 (Q queries)
solution : 4 3 4 0 0
3 1 (N Q)
3 2 1
2
solution : 3 2 1
提示是使用高级排序算法。
在第一个测试用例中：
第一个查询{4，3，4，3，0}
之后的数组第二个查询{4，3，4，0，0 } 之后的数组
我尝试了蛮力方法，遍历每个查询。无法提出一种有效的方法。
我首先误解了问题，并在何时解决了问题A[j] > A[I]（见下文），这似乎更有趣：）
为了解决的问题A[j] < A[I]，对于每个元素，我们想知道在元素可能被设置为零之前，左边是否有更大的元素要查询。惊喜！如果在查询之前将其置零，则意味着向左查询了更大的元素。
我们可以在O(n)时间和O(|Q|)空间上解决这个问题（假设我们使用输入空间作为输出）。将查询索引放在一组中以进行O(1)查找。从左到右遍历并保留最大查询元素的单个变量（起始值为0）。如果当前元素小于largest_seen_queried_element，则在输出中将其标记为零。如果查询了元素并且大于largest_seen_queried_element，则更新largest_seen_queried_element。
4 3 4 3 2
Queries 3 2
4 largest_queried 0
3 largest_queried 0
4 largest_queried 4
3 < 4 so set to 0 (largest_queried stays the same)
2 < 4 so set to 0
A[j] > A[i]我们可以在O(n log n)时间和O(n)空间上解决这个问题。假设所有非负元素，对于每个数组元素，我们想知道是否存在（1）被查询的左侧任何下部元素，或（2）给定的查询顺序作为时间，是否存在等于或更高的元素t在某个时间设为零之后，有时被查询的左边t' < t。
从左到右遍历该数组以及带有表示其顺序的其他时间标记的查询列表或映射（例如，[(1, 2), (2, 0)]将意味着在时间2查询索引1，在时间0查询索引2）。
维护一棵树，其中包含到目前为止查询到的所有元素的树（按其值排序），并用左侧子树中出现的最短时间进行装饰。如果在更早的时间出现相同的查询值，请更新时间修饰。
对于每个元素，在查询的元素树中查找值较低的最近节点。如果存在，则在输出中将该元素标记为0。如果还查询了元素，并且该时间晚于我们在树中找到的相应时间修饰，则将0与查询时间一起插入到所查询元素的树中（或者如果0已经存在，则更新时间修饰稍后再树）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句