这道题当然可以用线段树求解，但是有点大材小用。我的做法是对顶堆，用两个堆维护中位数。
建立一个大根堆，一个小根堆。大根堆存储前半部分序列，小根堆存储后半部分序列，在任意时刻，这个序列的中位数为大根堆的堆顶或者是小根堆的堆顶。
如果现在新加入了一个数x，判断x应该在大根堆还是小根堆中，即判断排序后x在序列的前半/后半部分。在任意时刻，若两个堆的元素个数之差大于1，我们就将元素多的堆的堆顶取出，放到另一个堆里，直到两个堆的元素个数之差不大于1，这样就能维护“在任意时刻，这个序列的中位数为大根堆的堆顶或者是小根堆的堆顶”的性质。
这就是“对顶堆”做法的全过程。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <cmath> 6 typedef long long ll; 7 inline int read() { 8 int ret=0,f=1; 9 char c=getchar(); 10 while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1;c=getchar();} 11 while(c<=‘9‘&&c>=‘0‘) ret=ret*10+c-‘0‘,c=getchar(); 12 return ret*f; 13 } 14 using namespace std; 15 priority_queue<int> q1; 16 priority_queue<int,vector<int>,greater<int> >q2; 17 int n; 18 int main() { 19 n=read(); 20 q1.push(read()); 21 printf("%d\n",q1.top()); 22 for(int i=2,x;i<=n;i++) { 23 x=read(); 24 if(x>q1.top()) q2.push(x); 25 else q1.push(x); 26 while(fabs(q1.size()-q2.size())>1) { 27 if(q1.size()>q2.size()) q2.push(q1.top()),q1.pop(); 28 else q1.push(q2.top()),q2.pop(); 29 } 30 if(i&1) printf("%d\n",q1.size()>q2.size()?q1.top():q2.top()); 31 } 32 return 0; 33 }
原文：https://www.cnblogs.com/shl-blog/p/10664904.html
