对顶堆
用于维护中位数。
维护两个 multiset，分别为 \(s1\) 与 \(s2\)。
\(s1\) 中存小于等于中位数的权值，\(s2\) 中存大于等于中位数的权值，且钦定 \(\text{size}(s1)≥\text{size}(s2),|\text{size}(s1)−\text{size}(s2)|≤1\)。
\(s1\) 中最大的数即为整个集合的中位数。
维护步骤：
- 先在 \(s1\) 中插入极小值，\(s2\) 中插入极大值。
- 对于插入操作，若 \(x\leq \text{max\{s1\}}\)，则将 \(x\) 插入 \(s1\)，否则插入 \(s2\)。
- 对于删除操作，先查询 \(s1\) 中有无，再查询 \(s2\) 中有无。
- 对于每次插入删除操作，都进行调整：若 \(\text{size}(s1)>\text{size}(s2) + 1\)，则不断取出 \(s1\) 的最大值插入 \(s2\)；若 \(\text{size}(s2)>\text{size}(s1)\)，则不断取出 \(s2\) 的最小值插入 \(s1\)。
- 调整完成后，\(s1\) 中最大的数即为集合的中位数。
multiset<int> s1;
multiset<int> s2;
void Init()
{
s1.clear();
s2.clear();
s1.insert(-INF);
s2.insert(INF);
}
void Change()
{
while (s1.size() > s2.size() + 1)
{
ll x = *(--s1.end());
s1.erase(--s1.end());
s2.insert(x);
}
while (s2.size() > s1.size())
{
ll x = *s2.begin();
s2.erase(s2.begin());
s1.insert(x);
}
}
void Insert(int x)
{
if (x <= *s2.begin())
{
s1.insert(x);
}
else
{
s2.insert(x);
}
Change();
}
void Del(int x)
{
auto it = s1.lower_bound(x);
if (it != s1.end())
{
s1.erase(it);
}
else
{
it = s2.lower_bound(x);
s2.erase(it);
}
Change();
}
int Zhong()
{
return *s1.rbegin();
}