题目描述

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.

题解

有两种方法第一种就是直接离散化后，用权值线段树查询第k大就行。这里主要说一下第二种，也就是对顶堆做法，
顾名思义，对顶的堆：一个最小值在前qq，一个最大值在前q，那么我们在不断插入数据的时候只要一直维护q最大值小于qq中最小值，并且q.size()==qq.size() OR q.size()==qq.size()+1即可

对顶堆代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 4e5 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

int t,n,m,a[maxn],ans[maxn];
priority_queue<int>q;
priority_queue<int,vector<int>,greater<int> >qq;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        while(q.size()) q.pop();
        while(qq.size()) qq.pop();
        int cnt=0;
        printf("%d %d\n",n,(m+1)/2);

        for(int i=1;i<=m;i++){
             if(i&1) q.push(a[i]);
             else qq.push(a[i]);
             if(i>=2){
                if(q.top()>qq.top()){
                    int x=q.top(),y=qq.top();
                    q.pop();qq.pop();
                    q.push(y);qq.push(x);
                }
             }
             if(i&1) ans[++cnt]=q.top();
        }

        for(int i=1;i<=cnt;i++){
            printf("%d",ans[i]);
            if(i%10==0) printf("\n");
            else {
                if(i==cnt) printf("\n");
                else printf(" ");
            }
        }
    }
}

权值线段树代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 4e5 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

int t,n,m,a[maxn],b[maxn],ans[maxn];
int sum[maxn];
void update(int rt,int l,int r,int pos){
     if(l==r) {sum[rt]++;return ; }

     int mid=(l+r)>>1;
     if(pos<=mid) update(rt<<1,l,mid,pos);
     else update(rt<<1|1,mid+1,r,pos);
     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

int ask(int rt,int l,int r,int pos){
    if(l==r){return l;}
    int mid=(l+r)>>1,cnt=sum[rt<<1];
    if(pos<=cnt) return ask(rt<<1,l,mid,pos);
    else return ask(rt<<1|1,mid+1,r,pos-cnt);
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) scanf("%d",&a[i]),b[i]=a[i];
        printf("%d %d\n",n,(m+1)/2);
        sort(b+1,b+1+m);
        n=unique(b+1,b+1+m)-b-1;
        int c=0;
        for(int i=1;i<=m;i++){
            update(1,1,n,lower_bound(b+1,b+1+n,a[i])-b);
            if(i&1){
                ans[++c]=b[ask(1,1,n,(i+1)/2)];
            }
        }

        for(int i=1;i<=c;i++){
            printf("%d",ans[i]);
            if(i%10==0) printf("\n");
            else {
                if(i==c) printf("\n");
                else printf(" ");
            }
        }
        for(int i=0;i<=4*n+10;i++) sum[i]=0;
    }
}