bzoj 5059: 前鬼后鬼的守护

.

题意：一个序列，把其中一个数$a$改成$b$的代价是$|a-b|$，求使序列不下降的最小代价。
题解：可并堆
最后的序列可以分成许多个区间，一个区间里的每个值都是一样的（两两不同时每个区间的长度为1）。如果一个区间要改成一个值，那么一定是它们的中位数。每次加入一个数就把它当成一个单独的区间，然后比较最后两个区间的中位数，假如前一个的比后一个的大，就把这两个区间合并，继续往前比较。用左偏树维护。具体看黄源河的论文里的例题。论文中把原题修改了一下，正好改成这题。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,a[500010],num=0;
struct tree
{
    int c,l,r,dis,sz;
    tree()
    {
        c=l=r=sz=0;
        dis=-1;
    }
}tr[500010];
struct que
{
    int l,r,c;
}q[500010];
long long ans=0;

int merge(int x,int y)
{
    if(x==0)
    return y;
    if(y==0)
    return x;
    if(tr[x].c<tr[y].c)
    swap(x,y);
    tr[x].r=merge(tr[x].r,y);
    if(tr[tr[x].l].dis<tr[tr[x].r].dis)
    swap(tr[x].l,tr[x].r);
    tr[x].dis=tr[tr[x].r].dis+1;
    tr[x].sz=tr[tr[x].l].sz+tr[tr[x].r].sz+1;
    return x;
}
int pop(int x)//返回新根 
{
    return merge(tr[x].l,tr[x].r);
}
int top(int x)
{
    return tr[x].c;
}
int ins(int x)
{
    int i=++num;
    tr[i].c=x;
    tr[i].l=tr[i].r=tr[i].dis=0;
    tr[i].sz=1;
    return i;
}
int md(int x)
{
    return x-x/2;
}
int main()
{
    scanf("%d",&n);
    int ed=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        q[++ed]={i,i,ins(a[i])};
        while(ed>=2&&top(q[ed-1].c)>top(q[ed].c))
        {
            q[ed-1].c=merge(q[ed-1].c,q[ed].c);
            q[ed-1].r=q[ed].r;
            while(tr[q[ed-1].c].sz>md(q[ed-1].r-q[ed-1].l+1))
            q[ed-1].c=pop(q[ed-1].c);
            ed--;
        }
    }
    for(int i=1;i<=ed;i++)
    {
        for(int j=q[i].l;j<=q[i].r;j++)
        ans+=abs(top(q[i].c)-a[j]);
    }
    printf("%lld",ans);
}