P1168 中位数（对顶堆）

Arce

题意：维护一个序列，两种操作
1、插入一个数
2、输出中位数（若长度为偶数，输出中间两个较小的那个）
对顶堆
维护一个小根堆，一个大根堆，大根堆存1--mid，小根堆存mid+1---n
这样堆顶必有中位数。
每次操作后维护两个堆元素数量，保证一个比另一个多1或相等

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define love_nmr 0
#define nmr 100500
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int>p;
int n;
int m;
int tot1;
char olinr[200];
int tot2;
int a[nmr];
int main()
{
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i];
  sort(a+1,a+n+1);
  for(int i=1;i<=(n/2);i++)
  {
    p.push(a[i]);
    tot1++;
  }
  for(int i=(n/2)+1;i<=n;i++)
  {
    q.push(a[i]);
    tot2++;
  }
  cin>>m;
  int x;
  while(m--)
  {
    cin>>(olinr+1);
    if(olinr[1]=='a')
    {
      cin>>x;
      if(x<p.top())
      {
        p.push(x);
        tot1++;
      }
      else
      {
        q.push(x);
        tot2++;
      }
    }
    else
    {
      if(tot2>tot1)
        cout<<q.top()<<endl;
      else 
        cout<<min(q.top(),p.top())<<endl;
    }
    while(tot2-1>tot1)
    {
      tot2--;
      tot1++;
      p.push(q.top());
      q.pop();
    }
    while(tot2<tot1)
    {
      tot2++;
      tot1--;
      q.push(p.top());
      p.pop();
    }
  }
  return love_nmr;
}

----olinr