算法

从x=n向x=1倒推，set维护可选择的点，以及最远的贡献值。最远点的贡献值是该点权值加上该点与次远点距离差的二倍。
ps:最远点可以更换成次远点；次远点被更换时，最远点的贡献也要更新。

时间复杂度

$nlog(n)$

C++ 代码

#include <iostream>
#include <set>
using namespace std;
typedef long long LL;
struct Node {
    int x;
    LL s;
    bool operator < (const Node& b) const {
        if(s==b.s) return x<b.x;
        return s<b.s;
    }
};
set<Node> q;
set<int> pos;
const int N=100010;
LL ans[N],a[N],b[N],sum;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>b[i];
    }
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(i!=n) q.insert({i,a[i]});
        sum+=a[i];
        pos.insert(i);
    }
    q.insert({n,a[n]+b[n]*2-b[n-1]*2});
    LL last=a[n]+b[n]*2-b[n-1]*2;
    sum=sum+b[n]*2;
    ans[n]=sum;
    int r=n;
    while(q.size()){
        if(q.size()==1){
            ans[1]=sum;
            break;
        }
        auto it=q.begin();
        if(it->x==r){
            sum=sum-b[r]*2-a[r];
            sum=sum+b[r-1]*2;
            auto y=q.find({r-1,a[r-1]});
            q.erase(*it);
            q.erase(*y);
            pos.erase(r);
            r--;
            q.insert({r,b[r]*2+a[r]-b[r-1]*2});
            last=b[r]*2+a[r]-b[r-1]*2;
        }
        else {
            auto y=pos.rbegin();
            ++y;
            if(*y==it->x){
                ++y;
                LL newsum=a[r]+b[r]*2-b[*y]*2;
                auto qt=q.find({r,last});
                q.erase(*qt);
                last=newsum;
                q.insert({r,newsum});
            }
            sum=sum-(it->s);
            pos.erase(it->x);
            q.erase(*it);

        }
        ans[q.size()]=sum;
    }
    for(int i=1;i<=n;++i)
    cout<<ans[i]<<endl;
    return 0;
}