Luogu

LOJ

分析

容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。

然而这样子边数是 $\mathcal{O}(n^2)$ 的，考虑一些优化。

考虑将 $a_i$ 离散化并建主席树，并在主席树上从上往下连边、叶子节点向对应的哨站连边，这样子哨站间连边时就可以直接找到对应版本的主席树然后向对应区间连边了。

然而有绝对值的问题，所以我们开两棵主席树分别维护正负，连边时一棵向前缀连边、一棵向后缀连边即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30000+10,M=300000+10;
const int inf=0x3f3f3f3f;

int n,W,cnt,a[N],u[N];

struct edge { int v,w,c,nxt; } e[M<<1];
int head[N];
void addEdge(int u,int v,int w,int c) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,c,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,-c,head[v]},head[v]=cnt;
}

int S,T;
int inq[N],lst[N]; ll dis[N];
int spfa() {
    memset(dis,0x3f,sizeof(dis)); memset(lst,0,sizeof(lst));
    queue<int> Q; Q.push(S); dis[S]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&dis[u]+e[i].c<dis[v]) {
                dis[v]=dis[u]+e[i].c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[T]!=0;
}

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
int rt[N][2],tot=0;
int id[N],ch[N][2];
void modify(int& o,int f,int l,int r,int pos,int v,int c) {
    o=++tot,ch[o][0]=ch[f][0],ch[o][1]=ch[f][1],id[o]=++cnt;
    if (l==r) { addEdge(id[o],v,1,c); return; }
    int mid=(l+r)>>1;
    if (pos<=mid) modify(ls(o),ls(f),l,mid,pos,v,c);
    else modify(rs(o),rs(f),mid+1,r,pos,v,c);
    if (ls(o)) addEdge(id[o],id[ls(o)],inf,0);
    if (rs(o)) addEdge(id[o],id[rs(o)],inf,0);
}
void link(int o,int l,int r,int ql,int qr,int u,int c) {
    if (!o) return;
    if (ql<=l&&r<=qr) { addEdge(u,id[o],1,c); return; }
    int mid=(l+r)>>1;
    if (ql<=mid) link(ls(o),l,mid,ql,qr,u,c);
    if (qr>mid) link(rs(o),mid+1,r,ql,qr,u,c);
}
#undef ls
#undef rs

int main() {
    n=read(),W=read();
    for (int i=1;i<=n;++i) u[i]=a[i]=read();
    sort(u+1,u+n+1); int c=unique(u+1,u+n+1)-u-1;
    for (int i=1;i<=n;++i) a[i]=lower_bound(u+1,u+c+1,a[i])-u;
    S=0,cnt=T=n<<1|1;
    for (int i=1;i<=n;++i) addEdge(S,i,1,0);
    for (int i=1;i<=n;++i) addEdge(i,T,1,W);
    for (int i=1;i<=n;++i) addEdge(i+n,T,1,0);
    for (int i=1;i<=n;++i) {
        modify(rt[i][0],rt[i-1][0],1,c,a[i],i+n,-u[a[i]]);
        modify(rt[i][1],rt[i-1][1],1,c,a[i],i+n,u[a[i]]);
    }
    for (int i=2;i<=n;++i) {
        link(rt[i-1][0],1,c,1,a[i],i,u[a[i]]);
        if (a[i]<c) link(rt[i-1][1],1,c,a[i]+1,c,i,-u[a[i]]);
    }
    ll ans=0;
    while (spfa()) {
        int f=inf;
        for (int i=lst[T];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (int i=lst[T];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=dis[T]*f;
    }
    printf("%lld\n",ans);
    return 0;
}