Luogu P4088 [USACO18FEB]Slingshot P 题解

(Updated: )
oi
,

Preface

题目链接

rua!调了半天发现原来是 $id$ 的问题。。。

Description

有一个数轴，上面有 $n$ 个传送门，使用第 $i$ 个传送门，你可以从 $x_i$​ 走到 $y_i$​，花费的时间为 $t_i$ 秒。你的速度为 $1$ 格/秒，有 $m$ 次询问，每次你要从 $a_i$​ 走到 $b_i$​，最多使用一次传送门，问最少需要多少秒。

$1\leq 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

// 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%10+'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;
}