题解 P2073 【送花】

· · 题解

本题中，需要使用线段树的地方并不是求和，而是确定价值最大（最小）的花的编号。

因为题中需要求的和是所有花的，所以只需要定义两个变量，插入花时对应相加，删除花时对应相减就行了。

首先，我们需要对每个插入的花进行标号。

但是我们发现，总是会有很多花被删除后留下了无用的空间。为了节省空间我们用一个队列记下被删除的花的编号，然后把它给下一个插入的花。

之后我们定义比较大小的方法：根据花的价值，将价值最大（最小）的编号放入线段树中。特别注意的是，空的单位以及被删除的花留下的空位是不能参与比较的。

之后就简单多了，需要的线段树的功能只有一个修改。再用STL里的map判重就行了。

代码如下：

#include<cstdio>
#include<queue>
#include<map>
#define CH ch=getchar()
using namespace std;
typedef long long LL;
int X,W;char ch;
inline int read()
{
    X=1,W=0;
    CH;
    while(ch<'0'||ch>'9'){if(ch=='-')X=-1;CH;}
    while(ch<='9'&&ch>='0'){W=W*10+ch-48;CH;}
    return X*W;
}
struct node{
    int w,c;
}a[500001];
struct tree{
    int l,r;
    int ma,mi;
}tr[2000001]; 
queue <int> zh;
map <int,bool> mp;
LL sumw,sumc;
int max(int _,int _1)
{
    if(a[_].c==0)return _1;
    else if(a[_1].c==0)return _;
    else return a[_].c>a[_1].c?_:_1;
}
int min(int _,int _1)
{
    if(a[_].c==0)return _1;
    else if(a[_1].c==0)return _;
    else return a[_].c<a[_1].c?_:_1;
}
void build(int k)
{
    int mid=(tr[k].l+tr[k].r)>>1;
    tr[k<<1].l=tr[k].l;
    tr[k<<1|1].l=mid+1;
    tr[k<<1].r=mid;
    tr[k<<1|1].r=tr[k].r;
    if(tr[k<<1].l!=tr[k<<1].r)build(k<<1);
    if(tr[k<<1|1].l!=tr[k<<1|1].r)build(k<<1|1);
    return;
}
void change(int k,int g)
{
    if(tr[k].l==g&&tr[k].r==g){
        tr[k].ma=tr[k].mi=g;
        return;
    }
    if(g<=tr[k<<1].r)change(k<<1,g);
    else change(k<<1|1,g);
    tr[k].ma=max(tr[k<<1].ma,tr[k<<1|1].ma);
    tr[k].mi=min(tr[k<<1].mi,tr[k<<1|1].mi);
}
int main()
{
    int op=read(),cnt=0,b,c,d,v,num=0;
    tr[1].r=500000,tr[1].l=1;
    build(1);
    while(op!=-1){
        if(op==1){
            b=read(),c=read();
            if(mp[c]==true){
                op=read();
                continue;
            }
            mp[c]=true;
            if(zh.empty()==false)d=zh.front(),zh.pop();
            else d=++cnt;
            a[d].w=b,a[d].c=c;
            sumw+=(LL)b,sumc+=(LL)c;
            change(1,d);
            num++;
        }
        if(op==2){
            if(num==0){
                op=read();
                continue;
            }
            v=tr[1].ma;
            zh.push(v);
            mp[a[v].c]=false;
            sumw-=(LL)a[v].w;
            sumc-=(LL)a[v].c;
            a[v]=a[0];
            change(1,v);
            num--;
        }
        if(op==3){
            if(num==0){
                op=read();
                continue;
            }
            v=tr[1].mi;
            zh.push(v);
            mp[a[v].c]=false;
            sumw-=(LL)a[v].w;
            sumc-=(LL)a[v].c;
            a[v]=a[0];
            change(1,v);
            num--;
        }
        op=read();
    }
    printf("%lld %lld",sumw,sumc);
    return 0;
}