中位数（权值线段树版）

中位数

题目描述

给定一个长度为 N N N 的非负整数序列 A A A，对于前奇数项求中位数。

输入格式

第一行一个正整数 N N N。

第二行 N N N 个正整数 A 1 … N A_{1\dots N} A1…N​。

输出格式

共 ⌊ N + 1 2 ⌋ \lfloor \frac{N + 1}2\rfloor ⌊2N+1​⌋ 行，第 i i i 行为 A 1 … 2 i − 1 A_{1\dots 2i - 1} A1…2i−1​ 的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

样例 #2

样例输入 #2

7
3 1 5 9 8 7 6

样例输出 #2

3
3
5
6

提示

对于 20 % 20\% 20% 的数据， N ≤ 100 N \le 100 N≤100；

对于 40 % 40\% 40% 的数据， N ≤ 3000 N \le 3000 N≤3000；

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 100000 1 \le N ≤ 100000 1≤N≤100000， 0 ≤ A i ≤ 1 0 9 0 \le A_i \le 10^9 0≤Ai​≤109。

代码

//权值线段树求中位数

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 1e5+10;

struct E{
    int l,r,cnt;
}tr[N<<2];

int n;
int w[N];
vector<int>nums;

int get(int x){
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

void pushup(int u){
    tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
}

void update(int u,int l,int r,int x){
    if(l==r){
        tr[u].cnt++;
        return; 
    }
    
    int mid=l+r>>1;
    
    if(x<=mid)update(u<<1,l,mid,x);
    else update(u<<1|1,mid+1,r,x);
    
    pushup(u);
    
}

int query(int u,int l,int r,int k){
    if(l==r){
        return nums[l];
    }
    
    int mid=l+r>>1;
    
    int c=tr[u<<1].cnt;
    if(k<=c)return query(u<<1,l,mid,k);
    return query(u<<1|1,mid+1,r,k-c);
}

int main(){
    cin>>n;
    
    for(int i=1;i<=n;i++){
        cin>>w[i];
        nums.push_back(w[i]);
    }
    
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    
    int tot=nums.size();
    for(int i=1,k=1;i<=n;i+=2,k++){
        if(i>1)update(1,0,tot-1,get(w[i-1]));
        update(1,0,tot-1,get(w[i]));
        cout<<query(1,0,tot-1,k)<<endl;
    }
    
    return 0;
}