首页
登录 | 注册

兹瓷查rank和kth的STL平衡树

stl

兹瓷查rank和kth的STL平衡树

明天就是一轮省选了啊。。这可能是退役前的最后一篇博文了吧(如果心情不好怕是连游记都会咕)

众周所知stl中有一个依靠红黑树实现的nb数据结构-std::set

但是这玩意儿没有维护siz域,也就是不能做类似于询问rank(i)(查询\(i\)的排名)和kth(i)(查询排名为\(i\)的数)

但是stl中还有一个更nb的东西-pb_ds中的平衡树

定义的话首先要引用

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

然后

__gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;

就可以啦

可以使用:

s.order_of_key(i)来得到值为\(i\)的数的排名

*s.find_by_order(i)来得到排名为\(i\)的数

复杂度比手写的慢很多,但大概还是log级别,所以考场上如果条件允许的话说不定可以救你一命~


相关文章

  • 查询数据库中所有表名 select table_name from information_schema.tables where table_schema='tools' and table_type='base table'; 查询指定 ...
  • 快三个月没写博客了,一直在忙着准备面试和去面试的路上,所以没时间写,也没什么想写的.现在告一段落,就总结一波! 面经 本人真的是双非一本.为什么加“真的”?因为有的人也写着"双非一本,进入阿里",但是某电子科技大学,比9 ...
  • 关于分布式锁原理的一些学习与思考-redis分布式锁,zookeeper分布式锁
      首先分布式锁和我们平常讲到的锁原理基本一样,目的就是确保,在多个线程并发时,只有一个线程在同一刻操作这个业务或者说方法.变量. 在一个进程中,也就是一个jvm 或者说应用中,我们很容易去处理控制,在jdk java.util 并发包中已 ...
  • Windbg分析高内存占用问题
    1. 问题简介 最近产品发布大版本补丁更新,一商超客户升级后,反馈系统经常奔溃,导致超市的收银系统无法正常收银,现场排队付款的顾客更是抱怨声声.为了缓解现场的情况, 客户都是手动回收IIS应用程序池才能解决. 这样的后果是很严重的,接到反馈 ...
  • More Effective C++
    More Effective C++ 35个改善编程与设计的有效方法 只有深入了解C++编译器如何解释代码, 才有可能用C++语言写出健壮的软件. C++的难学, 不仅在其广博的语法, 语法背后的语义, 语义背后的深层思维, 深层思维背后的 ...
  • 前言:取得成功的要自律!可能有一腔热血,努力很长一阵子,但过一阵子之后,就不坚持了,所以要自律去约束自己时刻坚持着! 一.收获 8月份的收获还是很大的,主要有以下几个方面: 学会了使用github 注册账号很长时间了,但不怎么会用,这个月, ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.080 s.
京ICP备10005923号