淋雨
题目描述
Moon发现自己来到了一个二维平面上，但是自己只能在
y
=
0
y=0
y
=
0
的直线上以不超过
v
c
m
/
s
v_cm/s
v
c
m
/
s
*的速度行走（可以折返回来走）。这个时候天空开始下了倾盘大雨，一共有
n
n
n
个雨滴，第个
i
i
i
雨滴以
v
g
m
/
s
v_gm/s
v
g
m
/
s
*的速度从
(
x
i
,
y
i
)
(x_i,y_i)
(
x
i
,
y
i
)
开始匀速下落，同时开始刮起了速度为
v
w
m
/
s
v_w m/s
v
w
m
/
s
，方向为x轴正方向的大风，可以认为每个雨滴在水平方向上有了和风速一样的速度，以及风不会影响人的行走速度。
Moon非常喜欢淋雨，为了简单起见把每个雨滴和Moon都视为是一个点，只有某个雨滴到达�
x
轴的位置的同时，Moon也正好在这个位置上，Moon才可以被这个雨滴淋到。现在给出q个询问，第i(1≤
i
≤
q
)次询问给出一个初始位置
(
s
i
,
0
)
(s_i,0)
(
s
i
,
0
)
，Moon想知道自己从
(
s
i
,
0
)
(s_i,0)
(
s
i
,
0
)
出发，在整个运动过程中，最多可以被多少个雨滴淋到呢？
分析
先分析一下每个雨滴落下至
x
x
x
轴的位置
p
p
p
和时间
t
t
t
：
不难得到
t
=
y
v
g
,
p
=
x
+
t
v
w
t=\frac y{v_g},p=x+tv_w
t
=
v
g
y
,
p
=
x
+
t
v
w
。
因为上面的柿子有分数，不好算，所以整体乘上一个
v
g
v_g
v
g
得到
t
=
y
,
p
=
x
+
t
v
w
t=y,p=x+tv_w
t
=
y
,
p
=
x
+
t
v
w
。
根据题意我们设
f
i
f_i
f
i
表示从第
i
i
i
个雨滴出发，最多能被多少个雨滴淋到。
转移就很显然了，
f
i
=
m
a
x
(
f
j
)
+
1
f_i=max(f_j)+1
f
i
=
ma
x
(
f
j
)
+
1
。
其中
i
i
i
与
j
j
j
应满足
∣
p
i
−
p
j
∣
≤
v
c
⋅
(
t
j
−
t
i
)
|p_i-p_j|\le v_c·(t_j-t_i)
∣
p
i
−
p
j
∣
≤
v
c
⋅
(
t
j
−
t
i
)
。
拆开绝对值并移项可得两条不等柿：
-
vc
⋅
t
i
−
p
i
≤
v
c
∗
t
j
−
p
j
v_c·t_i-p_i\le v_c*t_j-p_j
v
c
⋅
t
i
−
p
i
≤
v
c
∗
t
j
−
p
j
-
vc
⋅
t
i
+
p
i
≤
v
c
∗
t
j
+
p
j
v_c·t_i+p_i\le v_c*t_j+p_j
v
c
⋅
t
i
+
p
i
≤
v
c
∗
t
j
+
p
j
满足以上两条件的
i
i
i
均可向
j
j
j
转移，现在考虑怎么么求满足以上条件的最大
f
j
f_j
f
j
。
寄
x
=
v
c
⋅
t
i
−
p
i
,
y
=
v
c
∗
t
i
+
p
i
x=v_c·t_i-p_i,y=v_c*t_i+p_i
x
=
v
c
⋅
t
i
−
p
i
,
y
=
v
c
∗
t
i
+
p
i
，然后先对
x
x
x
排序，显然排序后第
i
i
i
个雨滴就可能从前
i
−
1
i-1
i
−
1
个雨滴转移过来，这样就满足了第一个条件。
因为我们只关心大小关系并且
y
y
y
的值可能很大，所以对
y
y
y
进行离散化至区间
[
1
,
n
]
[1,n]
[
1
,
n
]
。
然后我们把第
j
j
j
的雨滴以二元组
(
y
,
f
j
)
(y,f_j)
(
y
,
f
j
)
的形式插入树状数组，那么
f
i
f_i
f
i
就相当于是在
[
y
i
,
n
]
[y_i,n]
[
y
i
,
n
]
之中找
f
j
f_j
f
j
的最大值，这样就满足了第二个条件。
回到题目，他是有
q
q
q
个询问，每个询问表示从
(
s
,
0
)
(s,0)
(
s
,
0
)
出发最多可以被多少个雨滴淋到。
我们可以将
(
s
,
0
)
(s,0)
(
s
,
0
)
看做是一个雨滴，然后再计算它的
f
f
f
值。
发现在线没有不好处理，正难则反，那就离线处理，你不能每次询问都做一次dp。
先分别计算每个起点对应的
x
x
x
和
y
y
y
值然后对
x
x
x
进行排序，也要离散化。
考虑当前枚举到第
i
i
i
个起点，第
j
j
j
滴雨滴，那么只要每次把
x
j
≤
x
i
x_j\le x_i
x
j
≤
x
i
的雨滴的
f
j
f_j
f
j
都插入到树状数组里，最后输出
[
y
i
,
n
]
[y_i,n]
[
y
i
,
n
]
之间
f
j
f_j
f
j
的最大值即可。
最后树状数组维护的是前缀，所以要把所有的区间翻转一下。如
[
y
i
,
n
]
[y_i,n]
[
y
i
,
n
]
翻转成
[
1
,
n
−
y
i
+
1
]
[1,n-y_i+1]
[
1
,
n
−
y
i
+
1
]
。
时间复杂度
O
(
(
n
+
q
)
log
n
)
O((n+q)\log n)
O
((
n
+
q
)
lo
g
n
)
。
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
const int N=1e5+5;
int n,q,s,vc,vg,vw,y[N],tr[N],ans[N];
struct point{
int t,p,x,y,id;
bool operator<(const point& CXK)const{
return x>CXK.x||x==CXK.x&&y>CXK.y;
}
}c[N],ask[N];
inline void update(int x,int k){
for(;x<=n;x+=x&-x)
tr[x]=max(tr[x],k);
}
inline int getmax(int x){
int res=0;
for(;x>0;x-=x&-x) res=max(res,tr[x]);
return res;
}
void Init(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q>>vg>>vw>>vc;
for(re int i=1;i<=n;i++){
int x,y; cin>>x>>y;
c[i]={y,x*vg+y*vw,0,0,0};
}
for(re int i=1;i<=n;i++){
c[i].x=vc*c[i].t-c[i].p;
c[i].y=y[i]=vc*c[i].t+c[i].p;
}
}
signed main(){
Init();
for(re int i=1;i<=q;i++){
cin>>s; s*=vg;
ask[i]={0,s,-s,s,i};
}
sort(y+1,y+n+1);
sort(c+1,c+n+1);
sort(ask+1,ask+q+1);
for(re int i=1,j=1;i<=q;i++){
int ay=lower_bound(y+1,y+n+1,ask[i].y)-y;
while(c[j].x>=ask[i].x&&j<=n){
c[j].y=lower_bound(y+1,y+n+1,c[j].y)-y;
update(n-c[j].y+1,getmax(n-c[j].y+1)+1);
j++;
}
ans[ask[i].id]=getmax(n-ay+1);
}
for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
return 0;
}