我有一个不一定排序的数组。我必须对其执行 Q 查询。 查询是这样的: 给定数组和索引 I。我必须将该数组中的所有元素从索引 i+1 更新到 n，这样 A[I]>A[j]。 查询相互依赖，即对查询 1 所做的更改将反射(reflect)在查询 2 中。
对每个查询所做的更改如下:
for j=I+1 to N:
if A[j]<A[I]:
A[j]=0
我不知道如何解决这个问题。我在想一些类似于二叉索引树的东西。但我不确定。在提示中，它说要使用高级排序算法。
最佳答案
这是 O((q+n) log n) 方法:
- 为给定数组的范围最小查询构建线段树
- 同时创建一个标记为[]的数组来跟踪应该设为零的节点
- 现在对于每个查询:如果给定索引 I 被标记，则什么都不做(您没有为元素提供约束，所以我假设所有 A[i] >=0)
- 如果没有标记我们可以在区间[I+1,n]中找到一些索引j使得A[j]是这个区间中的最小值
- 如果这样的 A[j] 是 >= A[i] 我们就不会进行查询
- 否则:
- 标记索引j, (marked[j] = true)
- 将线段树设置位置 j 更新为某个大值(无穷大)
- 从第 4 步开始继续执行，直到我们完成查询
这可能看起来很慢，因为对于每个查询，我们可能在线段树中进行 n 次更新，但我们可以注意到每个元素最多被标记一次，所以最坏的情况是 O((q+n) log n)
关于algorithm - 元素数组的多个查询更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57944414/