map/set/multiset里有询问排名的操作吗？

WJnY @ 2024-11-28 09:43:06

by LG_jyc @ 2024-11-28 09:49:47

@WJnY

询问排名为k的数可以通过迭代器从begin()向后移动k-1步实现，详情请看 advance()

by zhujiangyuan @ 2024-11-28 09:54:18

可以使用 pbds 的平衡树。

by xfrvq @ 2024-11-28 09:54:37

@WJnY 没有 O(\log) 复杂度查询排名/排名为k的数的操作。

by FFTotoro @ 2024-11-28 09:55:29

@WJnY std::set 不支持这种操作，只有像楼上所述的 O(n) 暴力移动指针。

建议学习 pbds 库中的 tree，这是一份不错的教程。__gnu_pbds::tree 是个功能更加强大的平衡树，支持了一些 std::set 不支持的操作。

by Ice_function @ 2024-11-28 15:29:45

@FFTotoro 是否确保 NOIP 一定可以用？谢谢。

by FFTotoro @ 2024-11-28 15:33:49

@Ice_function 可用。