AT_keyence2019_e题解

· · 题解

题意

给定一张 n 个点的完全图，(i,j) 间点的边权是 |i-j|\times D+a_{i}+a_{j}。

求这个图的最小生成树。

Solve

对于这种在边数爆炸的图上让你求最小生成树的题，很冷门的 Boruvka 算法可以发挥其神奇的作用。

Boruvka 算法考虑维护当前的连通块（刚开始时每个点都是一个连通块），然后对于每一个连通块，求其连到其他连通块的最小边。

然后向最小生成树中加入这些找到的边，重复两个操作直到整出生成树为止。

虽然每次找边的复杂度是 O(m) 的，但是很容易发现连通块的数量每次合并完都会少一半，所以一共只会合并 O(\log n) 次。

总复杂度的就是 O(n\log n) 的。

这个算法的优势就在于它只需要 \log 次合并，而且此算法可把问题转化为找连通块最小出边。

知道了这个算法后，本题基本就可以当个板子题做。

因为边权的式子比较坑，带了个绝对值，所以不妨开两发线段树，一发存 A_{i}-i，一发存 A_{i}+i。

这样每轮找边就是 n\log n 的，故总复杂度为 O(n\log^2n)，只要常数不是特别巨大即可通过。

注意：给一个连通块找出边的时候记得把这个连通块内的点在线段树上改成极大值！（找完后还得改回来！）

Code

不仅粪得不行还拥有巨大常数的屑代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<bitset>
#include<map>
#include<set>
#include<functional>
#include<queue>
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+5;
const ll inf=1e16;
template<typename T>
inline void scan(T& x)
{
    x=0;
    T dp=0;
    char type=getchar();
    while(type<'0') dp|=(type=='-'),type=getchar();
    while(type>='0') 
    {
        x=(x<<1)+(x<<3)+(type&15);
        type=getchar();
    }
    x=dp?-x:x;
}
template<typename T,typename ... args>
inline void scan(T& x, args& ... tmp)
{
    scan(x);
    scan(tmp...);
    return ;
}
template<typename T>
inline void print(T x)
{
    if (x<0) putchar('-'),x=-x;
    if (!x) return ;
    print(x/10);
    putchar(x%10+'0');
}
int n;
struct SegmentTree
{
    struct Node
    {
        ll MMn;
        int Mp;
    }tree[N<<2];
    inline void pushup(int k)
    {
        if (tree[k<<1].MMn<tree[k<<1|1].MMn)
        {
            tree[k].MMn=tree[k<<1].MMn;
            tree[k].Mp=tree[k<<1].Mp;
        }
        else 
        {
            tree[k].MMn=tree[k<<1|1].MMn;
            tree[k].Mp=tree[k<<1|1].Mp;
        }
    }
    void build(std::function<ll(int)>f,int k=1,int l=1,int r=n)
    {
        if (l==r)
        {
            tree[k].MMn=f(l);
            tree[k].Mp=l;
            return ;
        }
        int mid=(l+r)/2;
        build(f,k<<1,l,mid);
        build(f,k<<1|1,mid+1,r);
        pushup(k);
    }
    void change(int pos,ll cag,int k=1,int l=1,int r=n)
    {
        if (l==r)
        {
            tree[k].MMn=cag;
            return ;
        }
        int mid=(l+r)/2;
        if (pos<=mid) change(pos,cag,k<<1,l,mid);
        else change(pos,cag,k<<1|1,mid+1,r);
        pushup(k);
    }
    std::pair<ll,int >query(int L,int R,int k=1,int l=1,int r=n)
    {
        if (L<=l&&r<=R) return std::pair<ll ,int >(tree[k].MMn,tree[k].Mp);
        int mid=(l+r)/2;
        std::pair<ll ,int >res(inf,-1);
        if (L<=mid) res=std::min(res,query(L,R,k<<1,l,mid));
        if (mid+1<=R) res=std::min(res,query(L,R,k<<1|1,mid+1,r));
        return res;
    }
}pre,suf;

int D,val[N];
inline ll F(int x)
{
    return (ll)-x*D+val[x];
}
inline ll G(int x)
{
    return (ll)x*D+val[x];
}
int tree[N],Size[N],last[N],Next[N];

/*DSU*/
inline int Find(int x)
{
    while (x!=tree[x])
        x=tree[x]=tree[tree[x]];
    return x;
}
inline bool Merge(int x,int y)
{
    x=Find(x),y=Find(y);
    if (x==y) return false;
    if (Size[x]>Size[y]) std::swap(x,y);
    Size[y]+=Size[y];
    tree[x]=y;
    return true;
}
int main()
{
    scan(n,D);
    for (int i=1;i<=n;i++)
        scan(val[i]);

    pre.build(F),suf.build(G);
    for (int i=1;i<=n;i++)
        tree[i]=i,Size[i]=1;

    ll ans=0;
    int tot=0;
    while (1)
    {
        if (tot==n-1) break;
        for (int i=1;i<=n;i++) last[i]=Next[i]=0;

        /*扣连通块*/
        for (int i=1;i<=n;i++)
        {
            Next[i]=last[Find(i)];
            last[Find(i)]=i;
        }

        std::vector<std::pair<int ,int > >edge;
        for (int i=1;i<=n;i++)
        {
            if (i!=Find(i)) continue;
            for (int pos=last[i];pos;pos=Next[pos])
                pre.change(pos,inf),suf.change(pos,inf);

            ll MMn=inf,sum;
            int x,y;
            for (int pos=last[i];pos;pos=Next[pos])
            {
                if (pos!=n)
                {
                    std::pair<ll ,int >R=suf.query(pos+1,n);
                    sum=R.first+F(pos);
                    if (R.second!=-1&&sum<MMn)
                    {
                        MMn=sum;
                        x=pos;
                        y=R.second;
                    }
                }
                if (pos!=1)
                {
                    std::pair<ll ,int >L=pre.query(1,pos-1);
                    sum=L.first+G(pos);
                    if (L.second!=-1&&sum<MMn)
                    {
                        MMn=sum;
                        x=pos;
                        y=L.second;
                    }
                }
            }
            if (MMn!=inf) edge.push_back(std::pair<int ,int >(x,y));

            for (int pos=last[i];pos;pos=Next[pos])
                pre.change(pos,F(pos)),suf.change(pos,G(pos));
        }

        for (auto [x,y]:edge)
        {
            int fx=Find(x),fy=Find(y);
            if (fx==fy) continue;
            /*启发式合并*/
            if (Size[fx]>Size[fy]) std::swap(fx,fy);
            ans+=(ll)D*std::abs(x-y)+val[x]+val[y];
            Size[fy]+=Size[fy];
            tree[fx]=fy;
            tot++;
        }
    }
    print(ans);
    return 0;
}