刷题总结——Middle number（ssoj 优先队列）

题目：

  给定一个整数序列··有两个操作：

  add x,表示序列中加入x

  mid 表示询问这个序列的中位数

  原始序列数量n<=100000,操作数m<=10000

题解：

  这道题可以直接用权值线段树做···先离散化一下就行··

  然而最快的方法是用优先队列··将先开始序列排序后分成左右两部分···左边用大根堆褚岑··右边用小根堆储存··在操作的时候维护即可··

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+5;
inline int R()
{
  char c;int f=0,i=1;
  for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
  if(c=='-')  c=getchar(),i=-1;
  for(;c<='9'&&c>='0';c=getchar())  f=(f<<3)+(f<<1)+c-'0';
  return f*i;
}
int num[N],T,n,m;
char s[5];
priority_queue<int>qmin;
priority_queue<int>qmax;
int main()
{
 // freopen("a.in","r",stdin);
  T=R();
  while(T--)
  {
    while(!qmin.empty()) qmin.pop();
    while(!qmax.empty()) qmax.pop();
    n=R();
    for(int i=1;i<=n;i++)  num[i]=R();
    sort(num+1,num+n+1);
    int t=1;
    if(n%2==1)  
      for(t=1;t<=(n+1)/2;t++)  qmax.push(num[t]);
    else 
    {  
      for(t=1;t<=n/2;t++)  qmax.push(num[t]); 
    }
    for(;t<=n;t++)  qmin.push(-num[t]);
    m=R();int a;
    for(int i=1;i<=m;i++)
    {
      scanf("%s",s);
      if(s[0]=='a')
      {
        a=R();
        if(a<qmax.top())  qmax.push(a);
        else qmin.push(-a);
        if(qmin.size()>qmax.size())
        {
          int r=-qmin.top();
          qmin.pop();qmax.push(r);
        }
        else if((qmax.size()-2)==qmin.size())
        {
          int l=qmax.top();
          qmax.pop();qmin.push(-l);
        }
      }
      else
        cout<<qmax.top()<<endl;
    }
  }
  return 0;
}