树状数组维护前缀和+二分查询
大体思路是:每当需要输出中位数的时候,我们实际只需要找到第(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;
}