AcWing 839. vector模拟平衡树薄纱multiset
原题链接
简单
作者:
y1_OneTap
,
2024-04-07 20:45:48
,
所有人可见
,
阅读 4
//vector模拟平衡树
#include<bits/stdc++.h>
using namespace std;
int n,idx;
vector<int> g;//升序
int cnt[1000010];
int main()
{
cin>>n;
while(n--)
{
string op;
cin>>op;
if(op=="I")
{
int x;
scanf("%d",&x);
g.insert(lower_bound(g.begin(),g.end(),x),x);
cnt[++idx]=x;
}
else if(op=="PM")
{
printf("%d\n",g[0]);
}
else if(op=="DM")
{
if(g.size())
g.erase(g.begin());
}
else if(op=="D")
{
int k;
scanf("%d",&k);
auto it=lower_bound(g.begin(),g.end(),cnt[k]);
if(it!=g.end())
g.erase(it);
}
else if(op=="C")
{
int k,x;
scanf("%d%d",&k,&x);
auto it=lower_bound(g.begin(),g.end(),cnt[k]);
cnt[k]=x;
if(it!=g.end())
g.erase(it);
g.insert(lower_bound(g.begin(),g.end(),x),x);
}
}
return 0;
}