大意：给出n个弹弓，可以用ti的时间把xi位置运到yi，在给出m组询问，求xj到yj最小时间。
sol：首先如果不用弹弓，时间应为abs（xj-yj）。否则时间就是abs（xi-xj）+abs（yi-yj）+ti。这就需要拆开绝对值用线段树来维护了。大力枚举四种情况，建四次线段树，就可以过了。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define int long long const int N=200005,inf=0x7fffffffffffff; int n,m,cnt=0,nn,hax[N],hay[N],ans[N]; struct node{int x,y,t,id;}p[N]; inline bool cmp(node aa,node bb){return (aa.x!=bb.x)?(aa.x<bb.x):(aa.y<bb.y);} struct segtree{int l,r,mi;inline int mid(){return (l+r)>>1;}}Tree[N<<2]; #define c1 x<<1 #define c2 x<<1|1 inline void Up(int x){Tree[x].mi=min(Tree[c1].mi,Tree[c2].mi);} inline void build(int l,int r,int x){Tree[x].l=l;Tree[x].r=r;if(l==r){Tree[x].mi=inf;return;}int mid=(l+r)>>1;build(l,mid,c1);build(mid+1,r,c2);Up(x);} inline void ins(int x,int po,int v){if(Tree[x].l==Tree[x].r){Tree[x].mi=min(Tree[x].mi,v);return;}int mid=Tree[x].mid();if(po<=mid)ins(c1,po,v);else ins(c2,po,v);Up(x);} inline int que(int l,int r,int x){if(Tree[x].l==l&&Tree[x].r==r)return Tree[x].mi;int mid=Tree[x].mid();if(r<=mid)return que(l,r,c1);else if(l>mid)return que(l,r,c2);else return min(que(l,mid,c1),que(mid+1,r,c2));} signed main() { freopen("1.in","r",stdin); int i,x,y,t; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++) { scanf("%lld%lld%lld",&x,&y,&t); p[++cnt]=(node){x,y,t,0}; hax[cnt]=x; hay[cnt]=y; } for(i=1;i<=m;i++) { scanf("%lld%lld",&x,&y); p[++cnt]=(node){x,y,0,i}; hax[cnt]=x; hay[cnt]=y; ans[i]=abs(x-y); }sort(hax+1,hax+cnt+1); sort(hay+1,hay+cnt+1); sort(p+1,p+cnt+1,cmp); nn=unique(hax+1,hax+cnt+1)-hax-1; for(i=1;i<=cnt;i++)p[i].x=lower_bound(hax+1,hax+nn+1,p[i].x)-hax; nn=unique(hay+1,hay+cnt+1)-hay-1; for(i=1;i<=cnt;i++)p[i].y=lower_bound(hay+1,hay+nn+1,p[i].y)-hay; build(1,cnt,1); for(i=1;i<=cnt;i++)if(!p[i].id)ins(1,p[i].y,-hax[p[i].x]-hay[p[i].y]+p[i].t);else ans[p[i].id]=min(ans[p[i].id],que(1,p[i].y,1)+hax[p[i].x]+hay[p[i].y]); build(1,cnt,1); for(i=1;i<=cnt;i++)if(!p[i].id)ins(1,p[i].y,-hax[p[i].x]+hay[p[i].y]+p[i].t);else ans[p[i].id]=min(ans[p[i].id],que(p[i].y,cnt,1)+hax[p[i].x]-hay[p[i].y]); build(1,cnt,1); for(i=cnt;i>=1;i--)if(!p[i].id)ins(1,p[i].y,+hax[p[i].x]+hay[p[i].y]+p[i].t);else ans[p[i].id]=min(ans[p[i].id],que(p[i].y,cnt,1)-hax[p[i].x]-hay[p[i].y]); build(1,cnt,1); for(i=cnt;i>=1;i--)if(!p[i].id)ins(1,p[i].y,+hax[p[i].x]-hay[p[i].y]+p[i].t);else ans[p[i].id]=min(ans[p[i].id],que(1,p[i].y,1)-hax[p[i].x]+hay[p[i].y]); for(i=1;i<=m;i++)printf("%lld ",ans[i]); }