OI康复训练 BZOJ 3196: Tyvj 1730 二逼平衡树 树套树

外层线段树,内层平衡树

操作一,就查每个区间比k小的数,合并就直接相加。

操作二,数有范围,二分一下,多一个log依旧可以过。

二分的时候我们让rank函数不返回rank,而返回比k小的数的个数,这样子就解决了一个数有多个,有些数不存在,二分混乱的问题。

操作三,先删,再插

操作四,求每个区间里k的前驱,合并取max

操作五,求每个区间里k的后继,合并取min

写得时候操作三的光处理了线段树和平衡树,用来记录序列的数组没修改,然而我操作三还会用到记录序列的数组,然后debug了一晚上。

发表评论