hello.

题解 P2073 【送花】

2018-02-28 22:27:47


思路

为什么标签那么吓人,其实优先队列强行模拟题意的操作是可行的,时间比Splay慢,但是依然只有488ms。

我们考虑开两个队列,分别维护最大值和最小值,同时用v数组建立价格到美丽值的映射。添加的时候直接两个队列都加上就行,并且更新v数组。

删除的时候,我们更新美丽值总和以及总价,同时把这个价格到美丽值的映射变成0。在以上操作之前,首先把队列中已经由于另一种操作删除的点pop掉,检测方法就是看这个点的价格对应的美丽值是不是已经变成了0,即已经被删除。

代码

尽量写得简介并且没有压行。有疑问欢迎交流。

#include <bits/stdc++.h>
#define maxn 1000001
using namespace std;
int v[maxn];//建立价格到美丽值的映射
long long tob,top;
priority_queue<int>qin;
priority_queue<int,vector<int>,greater<int> >qax;
void Add(){
    int x,y;
    cin>>x>>y;
    if (v[y]) return;//发现相同价格就返回
    qin.push(y);
    qax.push(y);
    v[y]=x;
    tob+=x,top+=y;
}
void Delin(){
    while(!qin.empty()&&!v[qin.top()]) qin.pop();
    if (!qin.empty()){
        int te=qin.top();
        tob-=v[te];
        top-=te;
        v[te]=0;
        qin.pop();
    }
}
void Delax(){
    while(!qax.empty()&&!v[qax.top()]) qax.pop();
    if (!qax.empty()){
        int te=qax.top();
        tob-=v[te];
        top-=te;
        v[te]=0;
        qax.pop();
    }
}
int main(){
    ios::sync_with_stdio(false);
    int q;
    cin>>q;
    while(q!=-1){
        if (q==1) Add();
        if (q==2) Delin();
        if (q==3) Delax();
        cin>>q;
    }
    cout<<tob<<" "<<top;
    return 0;
}