Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 自创算法：对顶堆算法在线求中位数 0MS

Posted by PoPoQQQ at 2014-06-11 21:14:54 on Problem 3784 and last updated at 2014-06-12 12:23:42
```对顶堆，又叫中根堆、上下堆，是一种可以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;
}
}
{
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++)
{
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");
}
}```

Followed by: