这题先定义一个大根堆（maxn）维护mid（n为奇数mid+1）的元素。再定义一个小根堆（minn）维护mid（n为奇数mid+1）到n的元素。然后对于插入元素的情况进行分类讨论。
当add x时
一.n 是奇数
1.从大根堆中取出元素y并弹出。
2.大根堆中插入元素min(x,y)。
3.小根堆中插入元素max(x,y)。
二.n 是偶数
1.从小根堆中取出元素y并弹出。
2.大根堆中插入元素min(x,y)。
3.小根堆中插入元素max(x,y)。
当询问时输出大根堆中的堆顶元素即可。
addmax（大根堆中元素个数） addmin（小根堆中元素个数） maxn（大根堆） minn（小根堆）
堆的操作(以大根堆为例)
1.堆的元素下调
void shiftdownmax(int x){
int t,flag=0;
while(x*2<=addmax&&flag==0){
if(maxn[x]<maxn[x*2])t=x*2;
else t=x;
if(x*2+1<=addmax){
if(maxn[t]<maxn[x*2+1])t=x*2+1;
}
if(t!=x){
swap(maxn[t],maxn[x]);
x=t;
}else flag=1;
}
}
2.堆的元素上调
void shiftdownmax(int x){
int t,flag=0;
while(x*2<=addmax&&flag==0){
if(maxn[x]<maxn[x*2])t=x*2;
else t=x;
if(x*2+1<=addmax){
if(maxn[t]<maxn[x*2+1])t=x*2+1;
}
if(t!=x){
swap(maxn[t],maxn[x]);
x=t;
}else flag=1;
}
}
3.建堆
由于堆的性质，只要调整一半的元素即可。
for(int i=1;i<=tmp;++i){
addmax++;
maxn[addmax]=a[i];
}
for(int i=addmax/2;i>=1;--i){
shiftdownmax(i);
}
4.取出元素
取出第一个元素将最后一个元素放在第一个元素的位置，并且元素个数减1，对堆顶进行下调操作。
int y=maxn[1];
maxn[1]=maxn[addmax--];
shiftdownmax(1);
5.加入元素
在堆尾加入新元素并且对其进行上调操作
maxn[++addmax]=min(x,y);
shiftupmax(addmax);
ac代码
#include<bits/stdc++.h>
using namespace std;
int n,m,x,addmax,addmin,a[100010],maxn[60010],minn[60010];
char str[5];
void shiftdownmax(int x){//大根堆向下调整
int t,flag=0;
while(x*2<=addmax&&flag==0){
if(maxn[x]<maxn[x*2])t=x*2;
else t=x;
if(x*2+1<=addmax){
if(maxn[t]<maxn[x*2+1])t=x*2+1;
}
if(t!=x){
swap(maxn[t],maxn[x]);
x=t;
}else flag=1;
}
}
void shiftdownmin(int x){//小根堆向下调整
int t,flag=0;
while(x*2<=addmin&&flag==0){
if(minn[x]>minn[x*2])t=x*2;
else t=x;
if(x*2+1<=addmin){
if(minn[t]>minn[x*2+1])t=x*2+1;
}
if(t!=x){
swap(minn[t],minn[x]);
x=t;
}else flag=1;
}
}
void shiftupmax(int x) {//大根堆向上调整
int flag=0;
if(x==1) return;
while(x!=1&&flag==0){
if(maxn[x]>maxn[x/2]) swap(maxn[x],maxn[x/2]);
else flag=1;
x=x/2;
}
}
void shiftupmin(int x) {//小根堆向上调整
int flag=0;
if(x==1) return;
while(x!=1 && flag==0){
if(minn[x]<minn[x/2]) swap(minn[x],minn[x/2]);
else flag=1;
x=x/2;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
addmax=0;
addmin=0;
sort(a+1,a+1+n);
if(n==1) maxn[++addmax]=a[1];//考虑特殊情况
else{
int tmp=n/2;
if(n%2) tmp++;
for(int i=1;i<=tmp;++i){
addmax++;
maxn[addmax]=a[i];
}
for(int i=addmax/2;i>=1;--i){
shiftdownmax(i);
}
for(int i=tmp+1;i<=n;++i){
addmin++;
minn[addmin]=a[i];
}
for(int i=addmin/2;i>=1;--i){
shiftdownmin(i);
}
}
scanf("%d",&m);
while(m--){
scanf("%s",str);
if(str[0]=='m'){
printf("%d
",maxn[1]);
}
else{
scanf("%d",&x);
if(n%2){
int y=maxn[1];
maxn[1]=maxn[addmax--];
shiftdownmax(1);
maxn[++addmax]=min(x,y);
shiftupmax(addmax);
minn[++addmin]=max(x,y);
shiftupmin(addmin);
n++;//记得更新n
}
else{
int y=minn[1];
minn[1]=minn[addmin--];
shiftdownmin(1);
minn[++addmin]=max(x,y);
shiftupmin(addmin);
maxn[++addmax]=min(x,y);
shiftupmax(addmax);
n++;
}
}
}
return 0;
}