自动搬运

查看原文

来自洛谷，原作者为

	foreverlasting 果然，失去别人远比自己离去更加令人恐惧。

搬运于2025-08-24 21:56:21，当前版本为作者最后更新于2018-09-27 19:52:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

扫描线+线段树。

被楼上震惊了，树套树什么的完全不会啊，表示萌新只会线段树。

首先转换题目，将题目转换成：

一个平面上有$n$个点，坐标为$(xi,yi)$，且每个点有一个点值$ti$。现有$m$个点$(ai,bi)$，使这$m$个点每个点与其他$n$个点的曼哈顿距离加上点值最小。说白了，就是$|ai-xi|+|bi-yi|+ti$最小，这也正是题目所求。

为什么要转换题目呢？因为这样会变得更加直观。我们分类讨论$a$与$x$，$b$与$y$的关系，用线段树+扫描线维护一下就好了。

code:

//2018.9.27 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register LL
#define LL long long
#define inf 0x3f3f3f3f3f3f3f
#define eps 1e-15
inline LL read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline LL _abs(const res &x){
    return x>0?x:-x;
}
inline LL _max(const res &x,const res &y){
    return x>y?x:y;
}
inline LL _min(const res &x,const res &y){
    return x<y?x:y;
}
const LL N=2e5+10;
namespace MAIN{
    struct P{
        LL x,y,t,opt,id;
        P() {}
        P(res x,res y,res t,res opt,res id):x(x),y(y),t(t),opt(opt),id(id) {}
    }pos[N];
    LL X[N],Y[N],n,m,cnt,nw;
    inline bool cmp(const P &a,const P &b){
        return a.x!=b.x?a.x<b.x:a.y<b.y;
    }
    namespace Segtree{
        LL mn[N<<2];
        inline void init(){
            memset(mn,inf,sizeof(mn));
        }
        inline void pushup(const res &rt){
            mn[rt]=_min(mn[rt<<1],mn[rt<<1|1]);
        }
        void update(const res &rt,const res &l,const res &r,const res &p,const res &v){
            if(l==r){mn[rt]=_min(mn[rt],v);return;}
            res mid=(l+r)>>1;
            if(p<=mid)update(rt<<1,l,mid,p,v);
            else update(rt<<1|1,mid+1,r,p,v);
            pushup(rt);
        }
        LL query(const res &rt,const res &l,const res &r,const res &L,const res &R){
            if(L<=l&&r<=R)return mn[rt];
            res mid=(l+r)>>1,ret=inf;
            if(L<=mid)ret=_min(ret,query(rt<<1,l,mid,L,R));
            if(R>mid)ret=_min(ret,query(rt<<1|1,mid+1,r,L,R));
            return ret;
        }
    }
    using namespace Segtree;
    LL ans[N];
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++){
            res x=read(),y=read(),t=read();
            pos[++cnt]=P(x,y,t,0,0);
            X[cnt]=x,Y[cnt]=y;
        }
        for(res i=1;i<=m;i++){
            res x=read(),y=read();
            pos[++cnt]=P(x,y,0,1,i);
            X[cnt]=x,Y[cnt]=y;
            ans[i]=_abs(x-y);
        }
        sort(X+1,X+cnt+1);
        nw=unique(X+1,X+cnt+1)-X-1;
        for(res i=1;i<=cnt;i++)pos[i].x=lower_bound(X+1,X+nw+1,pos[i].x)-X;
        sort(Y+1,Y+cnt+1);
        nw=unique(Y+1,Y+cnt+1)-Y-1;
        for(res i=1;i<=cnt;i++)pos[i].y=lower_bound(Y+1,Y+nw+1,pos[i].y)-Y;
        sort(pos+1,pos+cnt+1,cmp);
        init();
        for(res i=1;i<=cnt;i++){
            if(!pos[i].opt)update(1,1,cnt,pos[i].y,-X[pos[i].x]-Y[pos[i].y]+pos[i].t);
            else ans[pos[i].id]=_min(ans[pos[i].id],query(1,1,cnt,1,pos[i].y)+X[pos[i].x]+Y[pos[i].y]);
        }
        init();
        for(res i=cnt;i>=1;i--){
            if(!pos[i].opt)update(1,1,cnt,pos[i].y,X[pos[i].x]+Y[pos[i].y]+pos[i].t);
            else ans[pos[i].id]=_min(ans[pos[i].id],query(1,1,cnt,pos[i].y,cnt)-X[pos[i].x]-Y[pos[i].y]);
        }
        init();
        for(res i=1;i<=cnt;i++){
            if(!pos[i].opt)update(1,1,cnt,pos[i].y,-X[pos[i].x]+Y[pos[i].y]+pos[i].t);
            else ans[pos[i].id]=_min(ans[pos[i].id],query(1,1,cnt,pos[i].y,cnt)+X[pos[i].x]-Y[pos[i].y]);
        }
        init();
        for(res i=cnt;i>=1;i--){
            if(!pos[i].opt)update(1,1,cnt,pos[i].y,X[pos[i].x]-Y[pos[i].y]+pos[i].t);
            else ans[pos[i].id]=_min(ans[pos[i].id],query(1,1,cnt,1,pos[i].y)-X[pos[i].x]+Y[pos[i].y]);
        }
        for(res i=1;i<=m;i++)printf("%lld\n",ans[i]);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}