动态中位数

动态中位数

假设给你一个 $q$ 次查询，查询可能有插入、删除操作，完成每次操作都需要输出当前序列的中位数。

一、对顶堆维护 $O(nlogn)$

维护两个 $multiset$ ，一个 $p$ 存中位数及其之前的数，另一个 $q$ 存中位数之后的数90。

假设目前序列长度为 $n$ ，那么 $p.size()=(n+1)/2$ ，$q.size=n/2$。

$p$ 从大到小排序，$q$ 从小到大排序。

插入的时候，判断应该插到哪个容器中。

删除的时候，先判断这个数在 $p$ 中是否存在，如果存在则删除，否则在 $q$ 中删除。

最后每次操作完需要进行调整大小，直至 $0\le p.size()-q.size()\le 1$ 。

则中位数即 $p$ 的最大数。

struct MIDIUM{multiset<int>p,q;//p 从大到小 q从小到大void justify(){while(p.size()>q.size()+1){q.insert(*p.rbegin());p.erase(--p.end());}while(p.size()<q.size()){p.insert(*q.begin());q.erase(q.begin());}}void add(int x){if(!q.empty()&&x>=*q.begin())q.insert(x);else p.insert(x);        justify();}void del(int x){if(q.count(x))q.erase(q.lower_bound(x));else if(p.count(x))p.erase(p.lower_bound(x));justify();}int get_mid(){return *p.rbegin();}
};

二、树状数组求第 $k$ 大 $O(nlogn)$

可以将数据离散化之后，插入到树状数组里面，然后在树状数组上二分求前缀和第一个 $\le k$ 的即可，$k$ 就是中位数的位置。

struct MIDIUM{vector<int>c;int n;void init(int n){this->n=n;c=vector<int>(n+1,0);}void add(int i,int x){for(;i<=n;i+=lowbit(i)){c[i]+=x;}}int pre(int i){int ans=0;for(;i;i-=lowbit(i)){ans+=c[i];}return ans;}int get_kth(int k){int pos=0,v=0;for(int i=__lg(n);i>=0;i--){if(pos+(1<<i)<=n&&v+c[pos+(1<<i)]<k){pos+=(1<<i);v+=c[pos];}}return pos;}int get_mid(){return get_kth(pre(n)+1>>1);}
};