由于我不会讲对顶堆，所以这里直接传上一个巨佬的学习笔记。
对顶堆其实还是很容易理解的，想这题的时候自己猜做法也能把没学过的对顶堆给想出来。后来了解，对顶堆主要还是动态的在线维护集合$K$大值。当然也可以带删除。但是可能退化，具体见另外一个题的说明。
像这题维护中位数就是要求第$N/2+1$大的数，所以可以让大根堆维护前$n/2$项，小根堆维护后$n/2+1$项（这里指排好序的）。然后每次插入的时候及时调整即可，由于调整幅度不大，所以可以保证复杂度是$log$级别的。
代码被我写繁了因为我当时还不知道有对顶堆这玩意儿。当然你用其他数据结构来水这题也是可以的，我本来也想这么干。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl 9 using namespace std; 10 typedef long long ll; 11 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 12 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline T read(T&x){ 16 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 17 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 18 } 19 const int N=10000+7; 20 int T,n,THXORZ,x,y,cnt; 21 22 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 23 read(T);while(T--){ 24 priority_queue<int> mae; 25 priority_queue<int,vector<int>,greater<int> > ushiro; 26 read(THXORZ),read(n);printf("%d %d ",THXORZ,(n+1)>>1); 27 read(x);mae.push(x),ushiro.push(x);printf("%d ",x),cnt=1; 28 for(register int i=2;i<=n;++i){ 29 if(i&1){ 30 read(y);if(x>y)x^=y^=x^=y; 31 int mid=mae.top(); 32 if(x<=mid&&y>=mid)mae.push(x),ushiro.push(y); 33 else if(x<mid&&y<mid)mae.pop(),mae.push(x),mae.push(y),ushiro.push(mae.top()); 34 else ushiro.pop(),ushiro.push(x),ushiro.push(y),mae.push(ushiro.top()); 35 ++cnt;if(cnt>10)puts(""),cnt=1; 36 printf("%d ",mae.top()); 37 } 38 else read(x); 39 } 40 puts(""); 41 } 42 return 0; 43 }