元素数组上的多个查询更新

Question

我有一个不一定要排序的数组。我必须对它执行Q查询。查询如下:给定数组和索引I，我必须更新该数组中从索引i+1到n的所有元素，以便AI>Aj。查询是相互依赖的，即对查询1的更改将反映在查询2中。

对每个查询所做的更改如下：

for j=I+1 to N:
    if A[j]<A[I]:
      A[j]=0

我不知道如何处理这个问题。我在想一些类似二元索引树的东西。但我不确定。在提示中，它说要使用高级排序算法。

Answer 1

以下是O((q+n) log n)方法：

1. 为给定数组的范围最小查询构建段树
2. 还创建一个数组marked[]来跟踪应该变为零的节点。
3. 现在，对于每个查询:如果给定索引i被标记，什么也不做(您没有为元素设置约束，所以我假设所有的Ai >=0)
4. 如果没有标记，我们可以在区间I+1，n中找到一些索引j，使得Aj是这个区间中的最小值。
5. 如果这样的Aj是>= Ai，我们就不需要查询了。
6. 否则：
   • mark索引j，(标记j= true)
   • 将段树设置位置j更新为某个大值(无穷大)
   • 从步骤4继续执行步骤，直到查询完成。

​

这似乎很慢，因为对于每个查询，我们可能在段树中进行n次更新，但是我们可以注意到，每个元素最多只能标记一次，所以最糟糕的情况是O((q+n) log n)。