poj3784 Running Median[对顶堆]

由于我不会讲对顶堆，所以这里直接传上一个巨佬的学习笔记。

对顶堆其实还是很容易理解的，想这题的时候自己猜做法也能把没学过的对顶堆给想出来。后来了解，对顶堆主要还是动态的在线维护集合$K$大值。当然也可以带删除。但是可能退化，具体见另外一个题的说明。

像这题维护中位数就是要求第$N/2+1$大的数，所以可以让大根堆维护前$n/2$项，小根堆维护后$n/2+1$项（这里指排好序的）。然后每次插入的时候及时调整即可，由于调整幅度不大，所以可以保证复杂度是$log$级别的。

代码被我写繁了因为我当时还不知道有对顶堆这玩意儿。当然你用其他数据结构来水这题也是可以的，我本来也想这么干。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl

 using namespace std;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+;

 int T,n,THXORZ,x,y,cnt;

 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);

     read(T);while(T--){

         priority_queue<int> mae;

         priority_queue<int,vector<int>,greater<int> > ushiro;

         read(THXORZ),read(n);printf("%d %d\n",THXORZ,(n+)>>);

         read(x);mae.push(x),ushiro.push(x);printf("%d ",x),cnt=;

         for(register int i=;i<=n;++i){

             if(i&){

                 read(y);if(x>y)x^=y^=x^=y;

                 int mid=mae.top();

                 if(x<=mid&&y>=mid)mae.push(x),ushiro.push(y);

                 else if(x<mid&&y<mid)mae.pop(),mae.push(x),mae.push(y),ushiro.push(mae.top());

                 else ushiro.pop(),ushiro.push(x),ushiro.push(y),mae.push(ushiro.top());

                 ++cnt;if(cnt>)puts(""),cnt=;

                 printf("%d ",mae.top());

             }

             else read(x);

         }

         puts("");

     }

     return ;

 }