algorithm - 二叉索引树的应用

Question

我试图解决 this算法问题，我遇到了这个很好的解决方案:

"The idea is to treat the a_i, b_i and c_i asymmetrically. The BIT supports minimum queries for key intervals starting at 1. We use c_i as values and b_i as keys. Those are inserted in the order of increasing a_i. This way, for each a_i in turn, the data structure allows queries for the smallest value of c_j (possibly ∞) for b_j in [1..b_i) and a_j < a_i. We have c_j < c_i if and only if contestant i is not excellent."

source

现在我很难理解这个解决方案。

这是我对这个解决方案的理解:我知道二叉索引树用于回答查询，例如查找数组中区间的总和，它还支持元素更新。它分别以 O(logn) 时间复杂度执行这两个操作。现在这个解决方案说我们构建 BIT，键为 c_i，值为 b_i，基本上 b_i 是一个附加值每个节点都有。现在我们在树中插入 a_i 值递增的元素，这是我失去控制的地方。我们插入节点的顺序以及该部分后面的语句有什么关系，我不知道。

请帮助我理解这个解决方案的内容。

Answer 1

让我们找到所有非优秀的参与者。另一位参与者j可以比参与者更好i只有他的 a[j] < a[i] .因此，我们可以忽略所有 a[j] 值较大的参与者。 .这就是为什么我们按 a 对它们进行排序的原因.

这个条件是必要的，但还不够。我们还需要检查 b和 c .我们该怎么做？我们需要知道是否有一个人a[j] < a[i] (也就是说，在排序顺序中排在当前顺序之前的那个)这样他的 b[j] < b[i]和 c[j] < c[i] .我们构建一个 BIT(以 c[j] 作为键，b[j] 是值)来检查最后两个条件。很明显这样j当且仅当前缀 [0, c[i]) 上的最小值存在小于 b[i] .

综上所述，思路如下:我们按a[i]对它们进行排序然后忽略 a 的值.这样，我们就从 3-D 问题变成了 2-D 问题，这更容易解决(这就是顺序很重要的原因。拥有更大 a[i] 的人永远不会更好)。我们使用 BIT 来解决二维问题。