线段树优化建图 拓扑排序 6.22西安集训T1

题目链接

有一条无限长的数轴，上面有 nn 个坑，第 ii 个坑的位置为 x_ixi​。你将要在数轴上再放置 nn 个球，第 ii 个将要放到的位置为 y_iyi​。每当有一个球被放上去之后，它就会滚落到离它最近的一个坑里并填上那个坑。如果有两个坑都离它最近，那么它会落到左边的里面。

现在 xuanxuan001 可以决定 nn 个球的放置顺序，为了节省时间，xuanxuan001 希望球的滚动距离总和尽量短，但他太菜了，所以需要你来帮他求出最短总距离并构造一个对应方案。

分析

首先，通过题面给的几组样例，我们可以发现，为了使总距离最小，第一个球一定和第一个坑配对，第二个球一定和第二个坑配对。。。最后一个球和最后一个坑配对。否则，总距离可能变长。我们用  $P_ {i}^{}$  表示与 i 配对的坑。

其次，我们发现在放一个球 $i$ 之前，他的附近可能有比 $P_{i}^{}$ 更近的坑，那么这些更近的坑所配对的球一定要先于 i 放，由此我们想到拓扑排序。一条从i连向j的边表示，只有先放i才能放j，那么跑一遍拓扑排序即可。

但是，建边的最坏复杂度为 $n_{}^{2}$，因此我们需要用线段树优化建边。具体过程见代码，也可以去看P5025 [SNOI2017]炸弹

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+55;
int b[N],k[N],n,len;
struct node{
    int l,r,in;
}t[N];
struct edge{
    int to,nex;
}e[N<<2];
int cnt,head[N],dis[N],pos[N],in[N],ans[N],tot;
void adda(int u,int v){
    //cout<<"adda: "<<u<<" "<<v<<endl;
    e[++cnt].to=v;e[cnt].nex=head[u];head[u]=cnt;t[v].in+=1;
}
void build(int u,int L,int R){
    //cout<<u<<" "<<L<<" "<<R<<endl;
    t[u].l=L,t[u].r=R;
    if(L==R){
        pos[L]=u;
        return;
    }
    int M=(L+R)>>1;
    build(u<<1,L,M);build(u<<1|1,M+1,R);
    adda(u<<1,u);adda(u<<1|1,u);
}
void change(int u,int l,int r,int now){
    //cout<<u<<endl;
    int L=t[u].l,R=t[u].r;
    if(L>=l&&R<=r){
        adda(u,now);return;
    }
    if(L>r||R<l) return;
    int M=(L+R)>>1;
    change(u<<1,l,r,now);change(u<<1|1,l,r,now);
}
bool cmp(node a,node b){
    return a.in<b.in;
}
queue<int>q;
signed main(){
    freopen("nameless.in","r",stdin);
    freopen("nameless.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&k[i]);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        dis[i]=abs(b[i]-k[i]);
        len+=dis[i];
    }
    sort(k+1,k+1+n);sort(b+1,b+1+n);
    build(1,1,n);
    for(int i=1;i<=n;i++){
        int mn=b[i]-dis[i],mx=b[i]+dis[i];
        int r=lower_bound(k+1,k+1+n,mx)-k-1;
        int l=upper_bound(k+1,k+1+n,mn)-k-1;
        if(k[l]<mn) l++;
        if(k[r]>=mx) r--;
        if(l==i) l++;
        if(r==i) r--;
        if(l>r) continue;
        change(1,l,r,pos[i]);        
    }
    for(int i=1;i<=n;i++){
        if(t[pos[i]].in) continue;
        q.push(pos[i]);
        ans[++tot]=i;
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nex){
            int v=e[i].to;
            t[v].in--;
            if(!t[v].in){
                q.push(v);
                if(t[v].l==t[v].r) ans[++tot]=t[v].l;
            }
        }
    }
    cout<<len<<endl;
    for(int i=1;i<=tot;i++){
        printf("%lld ",ans[i]);
    }
    return 0;
}