中位数在线求法

O(Nlog⁡n)O(N\log n)

但是好像 O2O2 优化了好多 insertinsert 速度。

1
2
3
4
5
6
7
8
9
10
11
cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        //在指定位置之前插入那个数
        //此处upper和lower都行
        a.insert(lower_bound(a.begin(),a.end(),x),x);
        if(i%2==1){
            cout<<a[(i-1)/2]<<endl;
        }
    }

对顶堆 O(log⁡n)O(\log n)

中位数对顶堆求法。

维护一个大根堆，和一个小根堆，先往大根堆里丢一个数。

然后每次插入时如果 >> 大根堆堆顶，那么就丢小根堆里。

显然小根堆的元素都是满足大于大根堆的元素。

记得维护两个堆的大小差值不超过 11。

大根堆就是维护了一个前半段，小根堆就是维护了后半段，因此互扔，快速取到中间的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<int,vector<int>>q1;//max
priority_queue<int,vector<int>,greater<int>>q2;//min
int main(){
    int n;
    cin>>n;
    int x;
    cin>>x;
    q1.push(x);
    cout<<q1.top()<<endl;
    for(int i=2;i<=n;i++){
        cin>>x;
        if(x>q1.top()) q2.push(x);
        else q1.push(x);
        while(abs((int)q1.size()-(int)q2.size())>1){
            if(q1.size()>q2.size()){
                q2.push(q1.top());
                q1.pop();
            }
            else q1.push(q2.top()),q2.pop();
        }
        if(i%2==1){
            if(q1.size()>q2.size()){
                cout<<q1.top()<<endl;
            }
            else{
                cout<<q2.top()<<endl;
            }
        }
    }
    return 0;
}

权值线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int sum[N<<5];
int ls[N<<5],rs[N<<5];
int cnt;
int rt;
void ins(int &u,int l,int r,int x,int val){
    if(!u) u=++cnt;
    sum[u]+=val;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) ins(ls[u],l,mid,x,val);
    else ins(rs[u],mid+1,r,x,val);
}
int kth(int u,int l,int r,int k){
    if(l==r){
    	return l;
    }
    int num=sum[ls[u]];
    int mid=(l+r)>>1;
    if(k<=num) return kth(ls[u],l,mid,k);
    else return kth(rs[u],mid+1,r,k-num);
}

例题

链接

一个序列，你需要找到长度 ≥L\ge L 的一段连续区间，使得其中位
数最大。

n≤2×105n\le 2 \times 10^5

考虑二分答案，尝试验证是否存在中位数 ≥mid\ge mid，具体的，将
≥mid\ge mid 的元素置为 11，将 <mid< mid 的元素，置为 −1−1，则我们需要找到一段长度区间使得和非负。

具体的，做前缀和，对于 ii 找到最小的 jj 使得和为正，验证是否长度超过 LL，复杂度 O(nlog⁡n)O(n \log n)。

证明单调性：

若取得小于等于中位数的数显然一定存在区间之和 ≥0\ge 0，若大于则一定不存在一段区间满足中位数之和 >0>0。

因为我们二分的是一个中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
using namespace std;
const int N=2e5+8;
int a[N],n;
int b[N];
int m;
bool check(int mid){
    for(int i=1;i<=n;i++){
        b[i]=a[i]>=mid?1:-1;
        b[i]+=b[i-1];
    }
    int mn=0;
    for(int i=m;i<=n;i++){
        mn=min(mn,b[i-m]);
        if(b[i]>=mn) return 1;
    }
    return 0;
}
int main(){
    freopen("emotions.in","r",stdin);
    freopen("emotions.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=1,r=2e5;
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}

__END__