luogu2073

思路

真的不明白洛谷标签的意思。线段树？平衡树？难道这个题不就是用优先队列模拟吗。。。看见标签还以为读错题了

用一个pri数组的下标表示价格，里面存漂亮度。用两个优先队列，分别按升序降序储存价格，然后用两个变量W，C分别表示当前漂亮度和价格就可以模拟了。

注意一个坑点，这个题删除最小价格的编号为3，删除最大价格的编号为2.但是题目描述中把删除最小价格写在了前面。不仔细读题就只有10分了、、、

//以价格为下标，用数组pri记录每个价格的收益。
//用两个优先队列维护最大最小价格 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1000000+10;
priority_queue<ll>Max;
priority_queue<ll,vector<ll>,greater<ll> >Min;
ll Pri[N],W,C; 
ll read() {
    ll x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int main() {
    while(1) {
        int k=read();
        if(k==1) {
            ll w=read(),c=read();
            if(Pri[c]) continue;    
            W+=w;
            C+=c;
            Min.push(c);
            Max.push(c);
            Pri[c]=w; 
        }
        else if(k==3) {
            ll now=0;
            while(!Pri[now]&&!Min.empty()) {
                now=Min.top();
                Min.pop();
            }
            if(Pri[now]!=0) {
                W-=Pri[now];
                C-=now;
                Pri[now]=0;
            }
        }
        else if(k==2) {
            int now=0;
            while(!Pri[now]&&!Max.empty()) {
                now=Max.top();
                Max.pop();
            }
            if(Pri[now]) {
                W-=Pri[now];
                C-=now;
                Pri[now]=0;
            }
        }
        else {
            cout<<W<<" "<<C;
            return 0;
        }
    }
    return 0;
}