动态中位数
动态中位数
假设给你一个 q q q 次查询,查询可能有插入、删除操作,完成每次操作都需要输出当前序列的中位数。
一、对顶堆维护 O ( n l o g n ) O(nlogn) O(nlogn)
维护两个 m u l t i s e t multiset multiset ,一个 p p p 存中位数及其之前的数,另一个 q q q 存中位数之后的数90。
假设目前序列长度为 n n n ,那么 p . s i z e ( ) = ( n + 1 ) / 2 p.size()=(n+1)/2 p.size()=(n+1)/2 , q . s i z e = n / 2 q.size=n/2 q.size=n/2。
p p p 从大到小排序, q q q 从小到大排序。
插入的时候,判断应该插到哪个容器中。
删除的时候,先判断这个数在 p p p 中是否存在,如果存在则删除,否则在 q q q 中删除。
最后每次操作完需要进行调整大小,直至 0 ≤ p . s i z e ( ) − q . s i z e ( ) ≤ 1 0 \leq p.size()-q.size() \leq 1 0≤p.size()−q.size()≤1 。
则中位数即 p p 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 k k 大 O ( n l o g n ) O(nlogn) O(nlogn)
可以将数据离散化之后,插入到树状数组里面,然后在树状数组上二分求前缀和第一个 ≤ k \leq k ≤k 的即可, k 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);}
};