自动搬运

查看原文

来自洛谷，原作者为

	toolong114514 在知识的海洋里溺水

搬运于2025-08-24 23:05:46，当前版本为作者最后更新于2025-08-18 11:57:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

解题思路

我们不妨让时间拉长到原来的 $v_c$ 倍，那么人的移动速度就变成了 $1$，风速变成了 $\frac{v_w}{v_c}$，雨滴下落速度变成了 $\frac{v_g}{v_c}$。这样可以简化接下来的式子。

接下来计算出每个雨滴 $i$ 到达地面的时刻和此时的横坐标，分别记作 $t_i,pos_i$。由于时间不可倒流，所以淋雨有先后顺序，可以将雨滴按落地时刻从小到大排序后 DP。

我们不妨把 $q$ 个询问都看做落地时刻为 $0$ 雨滴参与 DP，只是其它的状态不能从此处转移。这些雨滴也没必要去排序，直接留在最前面。

定义 $f_i$ 表示钦定当前淋了第 $i$ 滴雨，以后总共能淋雨的最大滴数。

显然，$f_1-1,\cdots,f_q-1$ 即为询问的答案。

两个雨滴之间可以转移，当且仅当淋完一滴雨赶到另一滴雨落地处的时间小于等于落地时刻之差。

转移方程如下：

$$f_i=\min_{\forall j>i,\left|pos_i-pos_j\right|\le t_j-t_i}f_j+1 $$

直接以此转移，时间复杂度约为 $O(n^2)$，需要优化。

转移方程中的绝对值不太好处理，将其拆开如下：

$$f_i=\min\begin{cases}\min_{pos_i-pos_j\le t_j-t_i}{f_j+1}&pos_i\ge pos_j\\\min_{pos_j-pos_i\le t_j-t_i}{f_j+1}&pos_i<pos_j\end{cases} $$

整理可得

$$f_i=\min\begin{cases}\min_{pos_i+t_i\le pos_j+t_j}{f_j+1}&pos_i\ge pos_j\\\min_{pos_j-t_j\le pos_i-t_i}{f_j+1}&pos_i<pos_j\end{cases} $$

所有 $f_i$ 的转移显然是两组三维偏序的形式：

$$\begin{cases}t_i\le t_j\\pos_j\le pos_i\\pos_i+t_i\le pos_j+t_j\end{cases} $$$$\begin{cases}t_i\le t_j\\pos_j> pos_i\\pos_i-t_i\ge pos_j-t_j\end{cases} $$

直接无脑上 CDQ 分治优化 DP，第一维 sort 排序，第二维归并，第三维用树状数组维护最大值转移即可。

时间复杂度约为 $O(n\log^2{n})$，可以通过本题。

参考代码

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
typedef long double db;
const int N=5e5+10;
struct ccf{
	db pos,ti;
	int xld;
}dot[N];
bool cmp1(ccf pre,ccf nxt){
	return pre.ti<nxt.ti;
}
bool cmp2(ccf pre,ccf nxt){
	return pre.pos<nxt.pos;
}
bool cmp3(ccf pre,ccf nxt){
	return pre.pos>nxt.pos;
}
db v_w,v_g,v_c;
int n,q,ans;
int f[N];
db num[N];
int cnt;
int get_pos(db x){
	int l=1,r=cnt;
	while(l<=r){
		int mid=(l+r)/2;
		if(x<num[mid]) r=mid-1;
		else if(x>num[mid]) l=mid+1;
		else return mid;
	}
}
int lowbit(int x){return x&-x;}
int arr[N];
void upd(int x,int y){
	while(x<=cnt){
		arr[x]=max(arr[x],y);
		x+=lowbit(x);
	}
}
int ask(int x){
	int res=0;
	while(x>0){
		res=max(res,arr[x]);
		x-=lowbit(x);
	}
	return res;
}
void cdq(int l,int r){
	if(l==r){
		f[dot[l].xld]=max(f[dot[l].xld],1);
		return;
	}
	int mid=(l+r)/2;
	cdq(mid+1,r);
	cnt=0;
	for(int i=l;i<=r;i++){
		num[++cnt]=dot[i].pos+dot[i].ti;
	}
	sort(num+1,num+cnt+1);
	cnt=unique(num+1,num+cnt+1)-num-1;
	for(int i=1;i<=cnt;i++){
		arr[i]=0;
	}
	sort(dot+l,dot+mid+1,cmp2);
	sort(dot+mid+1,dot+r+1,cmp2);
	int i=l,j=mid+1;
	while(i<=mid){
		while(j<=r&&dot[i].pos>=dot[j].pos){
			if(dot[j].xld>q) upd(cnt-get_pos(dot[j].pos+dot[j].ti)+1,f[dot[j].xld]);
			j++;		
		}
		f[dot[i].xld]=max(f[dot[i].xld],(ask(cnt-get_pos(dot[i].pos+dot[i].ti)+1)+1));
		i++;
	}
	cnt=0;
	for(i=l;i<=r;i++){
		num[++cnt]=dot[i].pos-dot[i].ti;
	}
	sort(num+1,num+cnt+1);
	cnt=unique(num+1,num+cnt+1)-num-1;
	for(i=1;i<=cnt;i++){
		arr[i]=0;
	}
	sort(dot+l,dot+mid+1,cmp3);
	sort(dot+mid+1,dot+r+1,cmp3);
	i=l,j=mid+1;
	while(i<=mid){
		while(dot[i].pos<=dot[j].pos&&j<=r){
			if(dot[j].xld>q) upd(get_pos(dot[j].pos-dot[j].ti),f[dot[j].xld]);
			j++;		
		}
		f[dot[i].xld]=max(f[dot[i].xld],ask(get_pos(dot[i].pos-dot[i].ti))+1);
		i++;
	}
	sort(dot+l,dot+mid+1,cmp1);	
	cdq(l,mid);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q>>v_g>>v_w>>v_c;
	v_g/=v_c,v_w/=v_c;
	for(int i=q+1;i<=q+n;i++){
		db xx,yy;
		cin>>xx>>yy;
		dot[i].xld=i;
		dot[i].ti=yy/v_g;
		dot[i].pos=xx+v_w*dot[i].ti;
	}
	for(int i=1;i<=q;i++){
		cin>>dot[i].pos;
		dot[i].ti=0;
		dot[i].xld=i;
	}
	sort(dot+1,dot+n+q+1,cmp1);
	cdq(1,n+q);
	for(int i=1;i<=q;i++){
		cout<<f[i]-1<<'\n';
	}
	return 0;
}

AC record

Written by toolong114514 on 2025/8/18.