Luogu P4088 [USACO18FEB]Slingshot P 题解
Preface
题目链接
rua!调了半天发现原来是 id 的问题。。。
Description
有一个数轴，上面有 n 个传送门，使用第 i 个传送门，你可以从 x_i 走到 y_i，花费的时间为 t_i 秒。你的速度为 1 格/秒，有 m 次询问，每次你要从 a_i 走到 b_i，最多使用一次传送门，问最少需要多少秒。
1leq n ,m leq 10^5 ,0 leq a_i ,b_i leq 10^9
Solution
显然，对于第 j 个询问使用第 i 个传送门，需要 x_i -a_j y_i - b_j t_i 秒的时间。
考虑这个绝对值很像曼哈顿距离，于是可以把这道题转化：
平面上有 n 个点，第 i 个点位于 (x_i,y_i)，有点权为 t_i。有 m 次询问，要求与 (a_i,b_i) 的曼哈顿距离加上点权最小的点。
所以直接二维数点，暴力将绝对值拆开，分四类讨论即可。
Code
代码语言：javascript复制
// Problem: P4088 [USACO18FEB]Slingshot P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4088
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
// Auther: yzxoi
// Site: yzxoi.top
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}
using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}
using namespace FastIO;
Cn int N=100010;
int n,m,lsh[2][N<<1];
LL tr[N<<4],Ans[N<<1];
struct node{int x,y,t,id;}a[N<<1];
I int cmp(Cn node& x,Cn node& y){return x.x<y.x(x.x==y.x&&x.y<y.y);}
I void update(int x,int l,int r,int pos,LL v){
if(l==r) return void(tr[x]=min(tr[x],v));
int mid=l r>>1;
if(pos<=mid) update(x<<1,l,mid,pos,v);
else update(x<<11,mid 1,r,pos,v);
tr[x]=min(tr[x<<1],tr[x<<11]);
}
I LL query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R) return tr[x];
int mid=l r>>1;LL res=2e18;
if(L<=mid) res=min(res,query(x<<1,l,mid,L,R));
if(R>mid) res=min(res,query(x<<11,mid 1,r,L,R));
return res;
}
int main(){
read(n,m);for(RI i=1;i<=n;i ) a[i].id=-1,read(a[i].x,a[i].y,a[i].t),lsh[0][ lsh[0][0]]=a[i].x,lsh[1][ lsh[1][0]]=a[i].y;
for(RI i=n 1;i<=m n;i ) a[i].id=i-n,read(a[i].x,a[i].y),Ans[a[i].id]=abs(a[i].x-a[i].y),lsh[0][ lsh[0][0]]=a[i].x,lsh[1][ lsh[1][0]]=a[i].y;
for(RI i=0;i<2;i ) sort(lsh[i] 1,lsh[i] 1 lsh[i][0]),lsh[i][0]=unique(lsh[i] 1,lsh[i] 1 lsh[i][0])-lsh[i]-1;
for(RI i=1;i<=m n;i ) a[i].x=lower_bound(lsh[0] 1,lsh[0] 1 lsh[0][0],a[i].x)-lsh[0],a[i].y=lower_bound(lsh[1] 1,lsh[1] 1 lsh[1][0],a[i].y)-lsh[1];
sort(a 1,a m n 1,cmp);
memset(tr,127,sizeof(tr));for(RI t,i=1;i<=m n;i )
if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n m,1,a[i].y) lsh[0][a[i].x] lsh[1][a[i].y]);
else update(1,1,n m,a[i].y,-lsh[0][a[i].x]-lsh[1][a[i].y] a[i].t);
memset(tr,127,sizeof(tr));for(RI i=m n;i>=1;i--)
if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n m,a[i].y,n m)-lsh[0][a[i].x]-lsh[1][a[i].y]);
else update(1,1,n m,a[i].y,lsh[0][a[i].x] lsh[1][a[i].y] a[i].t);
memset(tr,127,sizeof(tr));for(RI i=1;i<=m n;i )
if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n m,a[i].y,n m) lsh[0][a[i].x]-lsh[1][a[i].y]);
else update(1,1,n m,a[i].y,-lsh[0][a[i].x] lsh[1][a[i].y] a[i].t);
memset(tr,127,sizeof(tr));for(RI i=m n;i>=1;i--)
if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n m,1,a[i].y)-lsh[0][a[i].x] lsh[1][a[i].y]);
else update(1,1,n m,a[i].y,lsh[0][a[i].x]-lsh[1][a[i].y] a[i].t);
for(RI i=1;i<=m;i ) writeln(Ans[i]);
return 0;
}
