【USACO18FEB】Slingshot

· · 题解

题面

扫描线+线段树。

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

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

一个平面上有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;
}