有序链表快速lower_bound [Codeforces 843B]

题目描述:给一个n个元素升序排列的链表,要求找到第一个>=x的元素值,n=50000,最多查询2000次

原理:链表中随机选取p(p 的范围大约是 [500, 1000])个位置,排序后做lower_bound,再从lower_bound-1开始向后查找直到>=x或到达lower_bound的位置

注意:如果lower_bound为第一个元素,则需要从头开始查找

无旋平衡树01Trie教程

基本原理:将整数分解为二进制数从高到低插入到Trie中,此时整棵树满足二叉查找树性质(注:只有叶子为实际节点,其他节点为虚拟节点,其实不完全满足二叉查找树性质),插入/删除同普通Trie,名次/Kth同普通二叉查找树,前驱 kth(rank(x)-1) 后继 kth(rank(x)+count(x))