bzoj 4585: [Apio2016]烟火表演【左偏树】

#include
#include
using namespace std;
const int N=600005;
int n,m,tot,fa[N],len[N],rt[N],d[N],cnt;
long long p[N],sum;
int read()
{
    int r=0,f=1;
    char p=getchar();
    while(p>‘9‘||p‘0‘)
    {
        if(p==‘-‘)
            f=-1;
        p=getchar();
    }
    while(p>=‘0‘&&p‘9‘)
    {
        r=r*10+p-48;
        p=getchar();
    }
    return r*f;
}
struct qwe
{
    int l,r,dis;
    long long v;
}e[N];
int hb(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(e[x].vif(e[e[x].l].disif(!e[x].r)
        e[x].dis=0;
    else
        e[x].dis=e[e[x].r].dis+1;
    return x;
}
int pop(int x)
{
    return hb(e[x].l,e[x].r);
}
int main()
{
    n=read(),m=read();
    for(int i=2;ifor(int i=m+n;i>1;i--)
    {
        long long l=0,r=0;
        if(iwhile(--d[i])
                rt[i]=pop(rt[i]);
            r=e[rt[i]].v;
            rt[i]=pop(rt[i]);
            l=e[rt[i]].v;
            rt[i]=pop(rt[i]);
        }
        e[++tot].v=l+len[i];
        e[++tot].v=r+len[i];
        rt[i]=hb(rt[i],hb(tot,tot-1));
        rt[fa[i]]=hb(rt[fa[i]],rt[i]);
    }
    while(d[1]--)
        rt[1]=pop(rt[1]);
    while(rt[1])
        p[++cnt]=e[rt[1]].v,rt[1]=pop(rt[1]);
    for(int i=1;i"%lld\n",sum);
    return 0;
}