题解 P3871 【[TJOI2010]中位数】

2018-11-01 16:09:34


要求中位数就要对数据排序。

维护一颗平衡树,资瓷插入和求中位数这两个操作。

求中位数可以视为求第 $k$ 大,这里的 $k=\frac{size[root]+1}{2}$

然后就可以用平衡树氵过去了。

用的是fhq treap,慢的很。

代码见blog