AT4569 Connecting Cities

· · 题解

题目传送门

考虑如何去掉这个绝对值，

换句话说，如何减少边数并且能建出 MST。

在求解偏序问题时，往往会分而治之，

这样原来 O(n^2) 的做法就能够被优化。

考虑将所有点对半折开，

左半部分和右半部分的建边分治处理，

只考虑横跨两部分的建边，

若左半部分的点为 j，右半部分的点为 i

边权就可以转换成：

(A_i+i\times d)+(A_j-j\times d)

既然 i 和 j 独立出来，那么只需要选出

右半部分 \min\{A_i+i\times d\} 所对应的 i，

左半部分 \min\{A_j-j\times d\} 所对应的 j，

将 j 与右半部分所有点连边，i 同理。

那么这样就只有 O(n\log n) 条边，

用 Kruskal 跑最小生成树就可以做到 O(n\log^2n)。

Code

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=200011; typedef long long lll;
struct node{int x,y; lll w;}e[N<<5];
lll a[N],b[N],D,ans; int n,f[N],m;
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans; 
}
bool cmp(node x,node y){return x.w<y.w;}
inline signed getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
inline void dfs(int l,int r){
    if (l==r) return;
    rr int mid=(l+r)>>1,t0=l,t1=r;
    for (rr int i=l;i<=mid;++i)
        if (a[t0]>a[i]) t0=i;
    for (rr int i=r;i>mid;--i)
        if (b[t1]>b[i]) t1=i;
    for (rr int i=l;i<=mid;++i)
        e[++m]=(node){i,t1,a[i]+b[t1]};
    for (rr int i=r;i>mid;--i)
        e[++m]=(node){t0,i,a[t0]+b[i]};
    dfs(l,mid),dfs(mid+1,r);
}
signed main(){
    n=iut(),D=iut();
    for (rr int i=1;i<=n;++i){
        rr int x=iut(); f[i]=i;
        a[i]=x-i*D,b[i]=x+i*D;
    }
    dfs(1,n),sort(e+1,e+1+m,cmp);
    for (rr int i=1;i<=m;++i){
        rr int fa=getf(e[i].x),fb=getf(e[i].y);
        if (fa!=fb) f[fa]=fb,ans+=e[i].w;
    }
    return !printf("%lld",ans);
}