在做 https://www.luogu.com.cn/problem/P3250 的时候发现的。
请你设计一个数据结构,使它能以 O(n)O(n)O(n) 的空间和均摊小常数 O(logn)O(\log n)O(logn) 在线完成以下操作:
* 添加一个数 x(1≤x≤109)x(1\le x\le 10^9)x(1≤x≤109)。
* 删除一个数 xxx,保证它存在。
* 查询最大值。
首先肯定想到的是平衡树,但是常数太大了;用权值树状数组的话,空间是 O(V)O(V)O(V) 的,开不下。
事实上,我们可以用两个大根堆来实现!
* 插入:向第一个大根堆内加入这个元素即可。
* 删除:运用 lazy-delete 的思想,先在第二个堆内加入这个元素,然后重复循环,如果两个堆顶相等的话,就删除两个堆的元素。显然这样可以得到最大值;由于一次操作只能添加一个元素,所以不论怎么删,总体都是均摊 O(logn)O(\log n)O(logn) 的。
由于堆的常数接近 111,所以这种做法远优于平衡树!