对顶堆，又叫中根堆、上下堆，是一种可以LOGN维护在线求中位数的算法
思想是维护两个堆，一个小根堆，一个大根堆，保证大根堆中的任意元素小于小根堆，并维护两堆元素数平衡
其中一堆堆顶即为中位数

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void swap(int &x,int &y){int z=x;x=y;y=z;}
int topheap[5010],toptop,bottomheap[5010],bottomtop;//两个堆，其中上堆是小根堆，下堆是大根堆 
void topinsert(int x)//上堆插入 
{
	topheap[++toptop]=x;
	int t=toptop;
	while(t>1&&topheap[t]<topheap[t>>1])
	swap(topheap[t],topheap[t>>1]),t>>=1;
}
void bottominsert(int x)//下堆插入 
{
	bottomheap[++bottomtop]=x;
	int t=bottomtop;
	while(t>1&&bottomheap[t]>bottomheap[t>>1])
	swap(bottomheap[t],bottomheap[t>>1]),t>>=1;
}
void toppop()//上堆弹顶 
{
    int t=2;
    topheap[1]=topheap[toptop];topheap[toptop--]=0;
    while(t<=toptop)
   	{	
   	    if(topheap[t]>topheap[t+1]&&t<toptop)t++;
   	    if(topheap[t]<topheap[t>>1])swap(topheap[t],topheap[t>>1]),t<<=1;
   	    else break;
   	}
}
void bottompop()//下堆弹顶 
{
    int t=2;
    bottomheap[1]=bottomheap[bottomtop];bottomheap[bottomtop--]=0;
    while(t<=bottomtop)
   	{	
   	    if(bottomheap[t]<bottomheap[t+1]&&t<bottomtop)t++;
   	    if(bottomheap[t]>bottomheap[t>>1])swap(bottomheap[t],bottomheap[t>>1]),t<<=1;
   	    else break;
   	}
}
void add(int x)//插入 
{
	if(x<=bottomheap[1])bottominsert(x);
	else topinsert(x);
	//插入，保证下堆的任意元素都小于等于上堆的任意元素  
	//注意一定要和下堆堆顶比较，因为第一次插入后元素一定在下堆，如果和上堆堆顶比较就会WA  
	while(toptop>bottomtop)bottominsert(topheap[1]),toppop();
	while(bottomtop>toptop+1)topinsert(bottomheap[1]),bottompop();
	//维护上下堆平衡，保证两堆元素数相等或下堆元素数比上堆元素数多1  
}
int ans[1010][5010];
int main()
{
	int p,i,j,k,x,m;
	scanf("%d",&p);
	for(j=1;j<=p;j++)
	{
		scanf("%d%d",&i,&m);
		memset(topheap,0,sizeof topheap);
		memset(bottomheap,0,sizeof topheap);
		toptop=bottomtop=0;
		for(k=1;k<=m;k++)
		{
			scanf("%d",&x);add(x);
			if(k&1)ans[i][++ans[i][0]]=bottomheap[1];
		}
	}
	for(i=1;i<=p;i++)
	{
		printf("%d %d\n",i,ans[i][0]);
		for(j=1;j<=ans[i][0];j++)
		{
			printf("%d",ans[i][j]);
			if(j!=ans[i][0])printf(" ");
			if(j%10==0)printf("\n");
		}
		printf("\n");
	}
}

• Re:OrzOrz (11) 140142 2015-07-25 09:12:37