P14030 【MX-X20-T4】「FAOI-R7」连接时光 I题解

· · 题解

题意：

题目说给定一个长度为 n 的数组 c，c 中的数可能为负数，你需要构造一个排列 a，当且仅当 1\le i<j\le n 且 a_i>a_j 时，i 会和 j 连一条边权为 c_j 的边，要求排列构造出的图联通且边权和最大。

题目分析：

我们先考虑都是正数的情况肯定就是边越多越好，对于每个点 i，它的边权 c_i 的贡献次数就为 1 到 i-1 中 a_j>a_i 的个数，我们要使这个个数尽量多，那么就从 n 排到 1 即可。我们受此启发，肯定正数的边尽量多，我们就先给数组中为正数的位置从大到小赋值，这样确保每个正数位置得到更多贡献且正数位置联通。

我们现在要使负数的点和正数的点联通且负数边权使用的尽量少，是负数边权尽量小，我们就先让正数点不贡献负数边权，即为将正数点从 1 开始标排列，这样一定不会给到负数边权。然后我们发现只要后面有正数点的负数点都一定在连通块内，我们给他们从小到大标号保证这些负数点之间不产生贡献。我们只用考虑最后一段连续负数点，我们先考虑将内部联通，我们肯定是找到当前未联通的块内负数边权最大的一个，并将前面的点连向它，然后继续找后面没有连的块。这样未联通部分就可以分为很多个联通的块，我们考虑如何将这些块连在一起。

为了不增加新的负贡献，我们只能连一条边，我们考虑每一个块的倒数第二个已经是最大的了再大一点也对当前块没有影响，下一个块的最后一个已经是下一个块最小的了再小一点对下一个块没有影响，它们交换后对两块之间也没有额外的贡献，我们就将下一个块的最后一个和这一个块的倒数第二个交换即可。若这个块长度为一，我们不难发现直接交换最后一个就可以了。

最后需要将负数块连向正数块，我们肯定还是选择负数块的最大权值，我们考虑不增加新的贡献就一定要交换前面最大的位置，这一定小于负数块最小的位置大于前面其他位置，前面若有负数就交换前面最后一个负数位置，否则就交换第一个正数位置，将它与第一个负数块的最后一个位置交换即可。

我们构造出来排列后就直接树状数组统计逆序对算答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
inline ll read(){
    ll w=0,f=1;
    char ch=getchar();
    while(ch<'0' || '9'<ch){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while('0'<=ch && ch<='9'){
        w=(w<<3)+(w<<1)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
int t,n,a[N],nxt[N];
ll c[N];
struct BIT{
    int tree[N];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void add(int x,int k){
        while(x<=n){
            tree[x]+=k;
            x+=lowbit(x);
        }
    }
    inline int query(int x){
        int res=0;
        while(x){
            res+=tree[x];
            x-=lowbit(x);
        }
        return res;
    }
    inline void clear(){
        for(int i=1;i<=n;i++) tree[i]=0;
        return;
    }
}tree;
signed main(){
    cin.tie(0);cout.tie(0);
    t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n;i++) c[i]=read(),a[i]=0,nxt[i]=0;
        int pos=0;
        for(int i=n;i>=1;i--){
            if(c[i]>=0){
                pos=i;
                break;
            }
        }
        vector<int> v;
        nxt[n]=n;
        v.push_back(n);
        for(int i=n-1;i>pos;i--){
            if(c[i]>=c[nxt[i+1]]){
                nxt[i]=i;
                v.push_back(i);
            }else nxt[i]=nxt[i+1];
        }
        v.push_back(pos);
        int cnt=n;
        for(int i=0;i<v.size()-1;i++){
            for(int j=v[i]-1;j>v[i+1];j--) a[j]=cnt--;
            a[v[i]]=cnt--;
            if(i>0){
                if(v[i]-1-v[i+1]>0) swap(a[v[i]-1],a[v[i-1]]);
                else swap(a[v[i]],a[v[i-1]]);
            } 
        }
        cnt=1;
        for(int i=pos;i>=1;i--){
            if(c[i]>=0) a[i]=cnt++;
        }
        int last=1;
        for(int i=1;i<pos;i++) if(c[i]<0) a[i]=cnt++,last=i;
        //cerr<<v.size()<<' '<<pos<<'\n';
        if(pos && pos!=n) swap(a[last],a[v[v.size()-2]]);
        ll ans=0;
        tree.clear();
        for(int i=1;i<=n;i++){
            ans+=(tree.query(n)-tree.query(a[i]))*c[i];
            tree.add(a[i],1);
        }
        write(ans);putchar('\n');
        for(int i=1;i<=n;i++) write(a[i]),putchar(' ');
        putchar('\n');
    }
    return 0;
}