algorithm - 成绩较好但jee排名较低的学生人数

Question

我们给了 n 个学生，每个学生都有 cgpa(大学成绩)和 jee ranks(入学考试成绩)。对于每个学生，我们必须计算 cgpa 较好但 jee rank 较差的学生人数。

(x1,y1), (x2,y2) ...(xi,yi)... (xn,yn)

对于每个 i，我们必须计算 no。 j 的 xj > xi 和 yj > yi(更差的排名意味着更高的排名。)

我可以想出以下 nlogn 算法- 对它们进行排序，降低 cgpa。 现在从左边开始扫描。 维护到目前为止在平衡二叉树中扫描的学生(根据他们的 jee 等级)。 对于下一个学生，通过查询平衡二叉树，找出已经扫描到的排名更高的学生数即可。

我不知道如何保持平衡的 bst，我可以返回 no。 O(logn) 中小于 k 的元素。我们需要保持不。每个节点的子树中的节点数。但是该怎么做呢？

要么帮助解决上述问题，要么提供不同的算法，也许是 DP。

Answer 1

如果您不想编写平衡二叉树代码，那么二叉索引树(又名 BIT 或 Fenwick 树)是您应该关注的 DS。它可以用 < 10 行简单的代码编写。 Here是我在 Fenwick Trees 上写的一篇博文，可能会有帮助。