https://www.luogu.com.cn/problem/P3871
看题解有好几种做法
1、对顶堆：用两个堆，分别是大顶堆和小顶堆，维护一个动态的有序序列
我们首先将所有的数丢进大根堆里然后取一半丢进小根堆里，这样就把所有的数分成了两段有序的部分。
加入操作可以每次取小根堆堆顶和加入的数比较，大于堆顶则加入小根堆否则加入大根堆（为了维护这个排序的有序性）。
而在询问时为了保证大根堆堆顶就是答案，我们要使大根堆里的元素等于（n+1）/2，所以加两个while循环控制它的元素个数（少了就从小根堆那里抢，多了就丢给小根堆），然后输出答案
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m;
priority_queue<int,vector<int>,greater<int> >que1;//xiao
priority_queue<int>que2;//da
string s;
int cnt1,cnt2;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
que2.push(a);cnt2++;
}
for(int i=1;i<=n/2;i++)
{
int x=que2.top();
que2.pop();cnt2--;
que1.push(x);cnt1++;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
cin>>s;
if(s[0]=='a')
{
int x;
scanf("%d",&x);
n++;
int l=que2.top();
if(x>l)que1.push(x),cnt1++;
else que2.push(x),cnt2++;
}
else
{
while(cnt2<(n+1)/2)
{
int x=que1.top();
que1.pop();cnt1--;
que2.push(x);cnt2++;
}
while(cnt2>(n+1)/2)
{
int x=que2.top();
que2.pop();cnt2--;
que1.push(x);cnt1++;
}
if(cnt2==(n+1)/2)
cout<<que2.top()<<endl;
}
}
return 0;
}
2、fhq treap
这个无旋treap本来就是维护动态序列的，所以可以拿来做（不要只会做模版）
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<ctime>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
const int maxn=200010;
const LL INF=1e18;
int n,val[maxn],rnd[maxn],son[maxn][3],size[maxn],num,m;
//val存权值，rnd存rand出的值，son存左右儿子，size存大小。
inline int newnode(int x){
++num;
size[num]=1;val[num]=x;rnd[num]=rand();
return num;
}
inline void update(int x){
size[x]=size[son[x][1]]+size[son[x][2]]+1;
}
inline void split(int &x,int &y,int k,int pos){ //拆分
if(!pos) x=y=0;
else{
if(val[pos]<=k){
x=pos;
split(son[pos][2],y,k,son[pos][2]); //左子树加一点右子树
}
else{
y=pos;
split(x,son[pos][1],k,son[pos][1]); //右子树加一点点左子树
}
update(pos);
}
}
inline int merg(int x,int y){ //合并
if(x==0||y==0) return x+y;
if(rnd[x]<rnd[y]){ //看谁当顶
son[x][2]=merg(son[x][2],y);
update(x);return x;
}
else{
son[y][1]=merg(x,son[y][1]);
update(y);return y;
}
}
inline int findd(int pos,int rank){
while(1){
if(size[son[pos][1]]>=rank){//在左子树里面去找
pos=son[pos][1];
}
else if(size[son[pos][1]]+1==rank) return pos;
else{
//在右子树里面去找，但是要去掉左子树的数量
rank-=size[son[pos][1]]+1;
pos=son[pos][2];
}
}
}
int main(){
srand((unsigned)time(NULL));
int op,x,y,root=0,m;
cin>>n;
for(int i=1;i<=n;i++){
cin>>op;
split(x,y,op,root); //插入一个数：维护treap的平衡，先按照输入的数拆分
root=merg(merg(x,newnode(op)),y); //再把这个数加进去合并起来
}
cin>>m;
string s;
for(int i=1;i<=m;i++){
cin>>s;
if(s[0]=='a'){
cin>>op;
split(x,y,op,root);
root=merg(merg(x,newnode(op)),y);
n++;
}
else{
int mid=(n+1)/2;
cout<<val[findd(root,mid)]<<endl;
}
}
return 0;
}