#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
#define T 1000000+50
#define inf 0x3f3f3f3f typedef long long ll;struct node1
{int v;node1(int _1):v(_1){}bool operator<(const node1& b)const{return v>b.v;}
};struct node2
{int v;node2(int _1):v(_1){}bool operator<(const node2& b)const{return v<b.v;}
};int a[T];
set<node1> se1;
set<node2> se2;
set<node1>::iterator it;
set<node2>::iterator itt;int main()
{
#ifdef zscfreopen("input.txt","r",stdin);
#endifint n,m,i,j,k,head,tail,size;while(~scanf("%d",&n)){se1.clear();se2.clear();head = tail = 0;while(n--){int u,v;scanf("%d",&u);if(u==1){scanf("%d",&v);a[tail++] = v;k = tail - head; if(se1.size()==0&&se2.size()==0){se2.insert(v);}else if(se1.size()<k/2){itt = se2.begin();int tmp = (*itt).v; if(tmp<v)se2.erase(itt),se2.insert(node2(v)),se1.insert(node1(tmp));else se1.insert(node1(v));}else{it = se1.begin();int tmp = (*it).v; if(tmp>v)se1.erase(it),se1.insert(node1(v)),se2.insert(node2(tmp));else se2.insert(node2(v));}}else if(u==2){it = se1.lower_bound(a[head++]);if((*it).v==a[head-1]&&it!=se1.end()){se1.erase(it);size = (se1.size()+se2.size())/2;while(se1.size()<size){itt = se2.begin();se1.insert(node1((*itt).v));se2.erase(itt);}}else{itt = se2.lower_bound(a[head-1]);se2.erase(itt);size = (se1.size()+se2.size())/2;while(se1.size()>size){it = se1.begin();se2.insert(node2((*it).v));se1.erase(it);}}}else {itt = se2.begin();printf("%d\n",(*itt).v);}}}return 0;
}
曾在网络游戏告白,但对方是假冒女生的人妖,而对此有阴影的郭大侠,坚持把游戏和现实分得清清楚楚。有一天竟被网络游戏中的女玩家告白了,虽然在游戏中接受了亚子的表白而结婚,但仍然不敢确信亚子就是真真正正的女生。终于有一天,卢西安所属四人公会的富豪会长决定举行线下聚会,结果发现四个人居然都是同一所高中的学生,甚至另外三人都是真真正正的可爱女孩子。
郭大侠还没完全接受这个事实时,他们发现亚子居然是重度的现实游戏混淆症患者,不仅在现实生活中用游戏角色名字“卢西安”叫人,还旁若无人黏住英骑身上。为了让亚子能够恢复正常,四人的游戏生活延续至学校。
……
今天,拯救亚子的计划是玩游戏!
这个游戏是这样的~
有一个像队列一样的东西,你可以push一个元素到这个队列的尾部,也可以pop掉这个队列的第一个元素
现在问题来了,这个队列中位数是多少呢?
中位数的定义为该队列升序排序后第k/2+1个的数的值,k为这个队列的大小
第一行一个nn,表示有n个操作
接下来nn行为这三个操作之一:
1 x,向这个队列推入一个数x
2,弹出这个队列的第一个数
3,查询这个队列的中位数是多少
1<=n<=10000001<=n<=1000000,保证输入都是在int范围的整数。
保证队列中的每个数都不一样哦~
对于每一个询问输出答案。
保证有解~
Sample Input | Sample Output |
---|---|
6 1 2 3 1 4 3 2 3 | 2 4 4 |
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态