树状数组维护前缀和+二分查询

大体思路是：每当需要输出中位数的时候，我们实际只需要找到第(now+1)/2小的点，所以我们可以使用前缀和来记录序列点的大小，然后通过二分查询下标来找到满足答案的解。（因为是前缀和所以保证了递增，或者说下标本身是递增的所以可以二分)。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int tot,num,n,x,p;
int a[10002],t[10002],d[10002];
int read(){int x=0,f=1;char s=getchar();while((s>'9')||(s<'0')) {if(s=='-')f=-1;s=getchar();}
    while((s<='9')&&(s>='0')) {x=x*10+s-'0';s=getchar();}return f*x;}
//简单读入优化
int lowbit(int x) { return x&(-x); }
int query(int x){ int ret=0; for(int i=x;i;i-=lowbit(i)) ret+=t[i]; return ret;}
void add(int x,int d){ if(x==0)return ; for(int i=x;i<=10000;i+=lowbit(i)) t[i]+=d;}
//树状数组维护前缀和。

void concrete(int *p){ memcpy(d,p,sizeof(d)); sort(d+1,d+1+n); for(int i=1;i<=n;i++)p[i]=lower_bound(d+1,d+1+n,p[i])-d;}
//离散化。



void solve(int cnt,int aim)
{
    int mid,l=1,r=10000,ret=0;
    while(l<=r)
    {
        mid=(l+r)/2;int result=query(mid);
        if(result>=aim) ret=mid,r=mid-1;
        else l=mid+1;
    }
    if(cnt%10==0) printf("%d\n",d[ret]);
    else printf("%d ",d[ret]);
}//二分查询
int main()
{
    tot=read();
    while(tot--)
    {
        num=read(),n=read();;int cnt=0;
        for(int i=1;i<=n;i++) a[i]=read();
        concrete(a);
        printf("%d %d\n",num,(n+1)/2);
        for(int i=1;i<=n;i++)
        {
            add(a[i],1);
            if(i%2) solve(++cnt,(i+1)/2);
        }
        if(cnt%10)puts("");
        memset(t,0,sizeof(t));
    }
    return 0;
}