Loading...

洛谷P2073 送花

check评论:0 条 remove_red_eye浏览量:403 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-12

权值线段树裸题

这道题好坑啊QAQ,$2$和$3$操作是反着给的...

其他的就很水了

#include <bits/stdc++.h>
using namespace std;
int tong[4000040],be[4000040],val[4000040];
int siz;
void ins(int o,int lf,int rg,int cos,int bea)
{
    if(lf==rg)
    {
        if(!tong[o])
        {
            tong[o]=1;
            be[o]=bea;
            val[o]=lf;
            siz++;
        }
        return ;
    }
    int mid=(lf+rg)>>1;
    if(cos<=mid)
    {
        ins(o<<1,lf,mid,cos,bea);
    }
    if(mid<cos)
    {
        ins(o<<1|1,mid+1,rg,cos,bea);
    }
    tong[o]=max(tong[o<<1],tong[o<<1|1]);
}
void delmin(int o,int lf,int rg)
{
    if(lf==rg)
    {
        tong[o]=0;
        be[o]=0;
        val[o]=0;
        return ;
    }
    int mid=(lf+rg)>>1;
    if(tong[o<<1])
    {
        delmin(o<<1,lf,mid);
    }
    else 
    {
        delmin(o<<1|1,mid+1,rg);
    }
    tong[o]=max(tong[o<<1],tong[o<<1|1]);
}
void delmax(int o,int lf,int rg)
{
    if(lf==rg)
    {
        tong[o]=0;
        be[o]=0;
        val[o]=0;
        return ;
    }
    int mid=(lf+rg)>>1;
    if(tong[o<<1|1])
    {
        delmax(o<<1|1,mid+1,rg);
    }
    else 
    {
        delmax(o<<1,lf,mid);
    }
    tong[o]=max(tong[o<<1],tong[o<<1|1]);
}
int dfsb(int o,int lf,int rg)
{
    if(lf==rg)
    {
        return be[o];
    }
    int mid=(lf+rg)>>1;
    int ans=0;
    ans+=dfsb(o<<1,lf,mid);
    ans+=dfsb(o<<1|1,mid+1,rg);
    return ans;
}
int dfsv(int o,int lf,int rg)
{
    if(lf==rg)
    {
        return val[o];
    }
    int mid=(lf+rg)>>1;
    int ans=0;
    ans+=dfsv(o<<1,lf,mid);
    ans+=dfsv(o<<1|1,mid+1,rg);
    return ans;
}
int main()
{
    int opt,x,y;
    while(scanf("%d",&opt),opt!=-1)
    {
        if(opt==1)
        {
            scanf("%d%d",&x,&y);
            ins(1,1,1000005,y,x);
        }
        if(opt==3)
        {
            if(!siz)
            {
                continue;
            }
            delmin(1,1,1000005);
            siz--;
        }
        if(opt==2)
        {
            if(!siz)
            {
                continue;
            }
            delmax(1,1,1000005);
            siz--;
        }
    }
    cout<<dfsb(1,1,1000005)<<" "<<dfsv(1,1,1000005);
} 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名