15011418730 LV 7 @ 2025-8-24 22:18:37

自动搬运

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:18:37，当前版本为作者最后更新于2020-02-27 19:47:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

\mathsf{Preface}

题面传送门。

感谢 @ $\color{black}\sf{c\color{red}henxia25}$ 在验题时的错误 idea 帮助我想到了复杂度更优的解法。

\mathsf{Solution}

$\sf{Subtask}\ 1$ ： $n\leq 5\times 10^2$ ， $q\leq 10^3$ 。

核心思想：“切割”。切割时间，使得每个时间段内小 A 和小 Y 都在做匀速直线运动（不改变方向和速度）。例如样例就可以切割成 $0.00\sim0.20$ ， $0.20\sim0.40$ ， $0.40\sim0.41$ ， $0.41\sim1.00$ 四个时间段。

不难发现，每个时间段内，小 A 和小 Y 的距离可能会： $(1)$ 不变。 $(2)$ 变小。 $(3)$ 变大。 $(4)$ 先变小再变大。

对于 $(1)$ ，我们特判一下。

对于 $(2,3)$ ，我们将其看做一个区间，有两个属性：距离 $[dl,dr]$ 和时间 $[tl,tr]$ 。

对于 $(4)$ ，我们可以三分找出其最小值，然后拆成两个区间。

最多会有 $n+m$ 个时间段，所以最多可能有 $2n+2m$ 个区间。计算区间可以设置 $eps$ ，也可以设置三分次数，时间复杂度用 $\log D$ 代替。

对于每个询问，特判后暴力算，找到区间后再二分 $[tl,tr]$ 找到时间。

时间复杂度 $O(n\log D+nq\log D)$ （下文中，假设 $n$ 的规模不小于 $m$ ） 实现起来简单，代码量约为 $\sf{2\sim2.5k}$ 。

代码（为了验题写的暴力）：

#include<bits/stdc++.h>
using namespace std;
#define ld long double
const int N=5e2+5;
const ld eps=1e-9;
bool Equal(ld x,ld y){return abs(x-y)<=eps;}
struct move{
	ld x,y,t;
}A[N],B[N];
struct query{
	ld c; int f;
}Q[N<<1];
int n,m,q,cnt;
vector <ld> inf,dis;
void Read(){
	cin>>n>>m>>q;
	cin>>A[0].x>>A[0].y>>B[0].x>>B[0].y;
	for(int i=1;i<=n;i++)cin>>A[i].x>>A[i].y>>A[i].t;
	for(int i=1;i<=m;i++)cin>>B[i].x>>B[i].y>>B[i].t;
	for(int i=1;i<=q;i++)cin>>Q[i].c>>Q[i].f,dis.push_back(Q[i].c);
}
struct seg{
	int pa,pb;
	ld l,r,Dl,Dr;
}S[N<<2];
void add(int pa,int pb,ld l,ld r,ld Dl,ld Dr){
	dis.push_back(Dl);
	dis.push_back(Dr);
	S[++cnt]=(seg){pa,pb,l,r,Dl,Dr};
}
ld cal(int pa,int pb,ld t){
	ld ra=(t-A[pa].t)/(A[pa+1].t-A[pa].t),rb=(t-B[pb].t)/(B[pb+1].t-B[pb].t);
	ld xa=A[pa].x+ra*(A[pa+1].x-A[pa].x),xb=B[pb].x+rb*(B[pb+1].x-B[pb].x);
	ld ya=A[pa].y+ra*(A[pa+1].y-A[pa].y),yb=B[pb].y+rb*(B[pb+1].y-B[pb].y);
	return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
void Break(){
	int pa=0,pb=0;
	while(pa<n){
		ld l=max(A[pa].t,B[pb].t),r=min(A[pa+1].t,B[pb+1].t);
		int Pa=pa,Pb=pb;
		if(r==A[pa+1].t)Pa++;
		if(r==B[pb+1].t)Pb++;
		ld Dl=cal(pa,pb,l),Dr=cal(pa,pb,r),Dm=cal(pa,pb,(l+r)/2);
		if(Equal(Dl,Dr)&&Equal(Dm,Dr)){
			inf.push_back(Dl);
			pa=Pa,pb=Pb;
			continue;
		}
		ld L=l,R=r;
		while(R-L>eps*3){
			ld ll=(L+R)/2,rr=ll+eps;
			ld Dll=cal(pa,pb,ll),Drr=cal(pa,pb,rr);
			if(Dll<Drr)R=rr;
			else L=ll;
		}
		if(Equal(l,L)||Equal(r,R))add(pa,pb,l,r,Dl,Dr);
		else{
			ld m=(L+R)/2; Dm=cal(pa,pb,m);
			add(pa,pb,l,m,Dl,Dm),add(pa,pb,m,r,Dm,Dr);
		}
		pa=Pa,pb=Pb;
	}
}
map <ld,int> mp;
void Discretize(){
	sort(dis.begin(),dis.end());
	int siz=unique(dis.begin(),dis.end())-dis.begin();
	for(int i=0;i<siz;i++)mp[dis[i]]=i;
}
void Answer(){
	for(int i=1;i<=q;i++){
		bool Inf=0;
		for(auto it:inf)if(Equal(it,Q[i].c))Inf=1;
		if(Inf){
			puts("-2.33");
			continue;
		}
		int ind=mp[Q[i].c];
		vector <ld> ans;
		for(int i=1;i<=cnt;i++){
			int L=mp[S[i].Dl],R=mp[S[i].Dr];
			if(i!=1)if(L>R)L--; else L++;
			if(L>R)swap(L,R);
			if(L<=ind&&ind<=R)ans.push_back(i);
		}
		if(ans.size()<Q[i].f){
			puts("-4.66");
			continue;
		}
		int pos=ans[Q[i].f-1],pa=S[pos].pa,pb=S[pos].pb,inc=S[pos].Dl<S[pos].Dr;
		ld L=S[pos].l,R=S[pos].r;
		while(R-L>eps*2){
			ld m=(L+R)/2,Dm=cal(pa,pb,m);
			if(inc&&Q[i].c<Dm||!inc&&Q[i].c>Dm)R=m;
			else L=m;
		}
		printf("%.8LF\n",L);
	}
}
int main(){
	Read();
	Break();
	Discretize();
	Answer();
	return 0;
}

$\sf{Subtask}\ 2$ ： $n\leq 2\times 10^4$ ， $q\leq 2\times 10^4$ 。

将所有区间的端点 $dl,dr$ 和询问距离离散化。询问时二分区间 $tl$ ，用树套树求出开始时间不大于二分的值且 $dl\leq c\leq dr$ 的区间个数并与 $f$ 比对，找到区间后像 $\sf{Subtask}\ 1$ 一样二分 $[tl,tr]$ 即可。需要注意区间边界的细节。

单次询问时间复杂度 $O(\log n^3+\log D)$ ，总时间复杂度 $O(n\log D+q\log^3n)$ ，常数较大，实现起来很麻烦，代码量约为 $\sf{5\sim6k}$ 。

其实一开始的 $\sf{std}$ 就是这个，但是 $\color{black}\sf{c\color{red}henxia25}$ 的错误 $\sf{idea}$ 让我探索到了更简单，也更快的算法，那就是 $\sf{Subtask}\ 3$ 。

$\sf{Subtask}\ 3$ ： $n\leq 4\times 10^4$ ， $q\leq 5\times 10^4$ 。

将所有距离离散化，然后我们需要求出的就是：每次给下标落在 $[l,r]$ 的数 $+1$ ，多次询问下标为 $c$ （离散化后）的值在第几次操作后等于 $f$ 。

每次操作后更新显然无法承受，但是我们有可持久化数组。

区间加法显然无法承受，但是我们有标记永久化。

这个可以用主席树 + 标记永久化轻松实现，查询的时候二分操作编号，求出区间后二分时间即可。同 $\sf{Subtask}\ 2$ 一样，需要注意区间边界的细节。

单次询问 $O(\log n^2+\log D)$ ，总时间复杂度 $O(n\log D+q\log^2n)$ 。常数大，空间复杂度 $O(q\log n)$ ，代码量约为 $\sf{3.5\sim 4k}$ 。

另外，浮点数的读入很慢，建议手写 $\sf{read}$ 。

#include<bits/stdc++.h>
using namespace std;
namespace IO{//手写 read 
	char buf[1<<23],*p1=buf,*p2=buf;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	inline void read(int &x){
		bool sign=0; char s=gc(); x=0;
		while(!isdigit(s))sign|=s=='-',s=gc();
		while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc();
		if(sign)x=-x;
	}
	inline void read(double &x){
		bool sign=0; char s=gc(); x=0;
		while(!isdigit(s))sign|=s=='-',s=gc();
		while(isdigit(s))x=x*10+s-'0',s=gc();
		x+=(gc()-'0')*0.1,x+=(gc()-'0')*0.01;
		if(sign)x=-x;
	}
}
using namespace IO;
const int N=1e5+5; const double eps=1e-9;
struct move {double x,y,t; bool operator < (const move &v) const {return t<v.t;} } a[N],b[N];
struct query {double c; int f;} c[N<<2];
struct section {double l,r,tl,tr; int pa,pb;} s[N<<2];
int n,m,q,cs,cnt,cinf;
double p[N<<4],inf[N<<1];
void Init(){
	read(n),read(m),read(q),read(a[0].x),read(a[0].y),read(b[0].x),read(b[0].y);
	for(int i=1;i<=n;i++)read(a[i].x),read(a[i].y),read(a[i].t);
	for(int i=1;i<=m;i++)read(b[i].x),read(b[i].y),read(b[i].t);
	for(int i=1;i<=q;i++)read(c[i].c),read(c[i].f),p[++cnt]=c[i].c;
}
bool Equal(double x,double y) {return abs(x-y)<=eps;}//判断两个数是否相等 
double Gap(double a,double b,double c,double d) {return sqrt((a-c)*(a-c)+(b-d)*(b-d));}//欧几里得距离公式
double Calc(int pa,int pb,double t){//求出某一时刻的距离
	double ra=(t-a[pa-1].t)/(a[pa].t-a[pa-1].t),rb=(t-b[pb-1].t)/(b[pb].t-b[pb-1].t);
	double xa=a[pa-1].x+(a[pa].x-a[pa-1].x)*ra,ya=a[pa-1].y+(a[pa].y-a[pa-1].y)*ra;
	double xb=b[pb-1].x+(b[pb].x-b[pb-1].x)*rb,yb=b[pb-1].y+(b[pb].y-b[pb-1].y)*rb;
	return Gap(xa,ya,xb,yb);
}
void Add(double x,double y,double l,double r,int pa,int pb) {s[++cs]={x,y,l,r,pa,pb},p[++cnt]=x,p[++cnt]=y;}//添加区间
void Breakmove(){//顾名思义，打破运动（求区间）
	sort(a+1,a+n+1),sort(b+1,b+m+1);
	int pa=1,pb=1;
	while(pa<=n&&pb<=m){
		double l=max(a[pa-1].t,b[pb-1].t),r=min(a[pa].t,b[pb].t),dl=Calc(pa,pb,l),dr=Calc(pa,pb,r);
		double m,d1,d2,ll=l,rr=r;
		int npa=pa+(r==a[pa].t),npb=pb+(r==b[pb].t);
		if(Equal(dl,dr)&&Equal(Calc(pa,pb,(l+r)/2),dr)) {inf[++cinf]=dl,pa=npa,pb=npb; continue;}//(1)，距离不变，infinity
		while(r-l>eps) {m=(l+r)/2,d1=Calc(pa,pb,m),d2=Calc(pa,pb,m+eps/3); d1<d2?r=m+eps/3:l=m;}//三分求最小值
		if(dl<d1||Equal(dl,d1)||Equal(d2,dr)||d2>dr)Add(dl,dr,ll,rr,pa,pb);//(2)(3) 
		else {m=(l+r)/2,d1=Calc(pa,pb,m); Add(dl,d1,ll,m,pa,pb),Add(d1,dr,m,rr,pa,pb);}//(4)
		pa=npa,pb=npb;
	}
}
int node,R[N<<2],laz[N<<8],ls[N<<8],rs[N<<8];
int Modify(int pre,int l,int r,int ql,int qr){//区间加+标记永久化 
	int id=++node,m=l+r>>1; laz[id]=laz[pre],ls[id]=ls[pre],rs[id]=rs[pre];
	if(ql<=l&&r<=qr) {laz[id]++; return id;}
	if(ql<=m)ls[id]=Modify(ls[pre],l,m,ql,qr);
	if(m<qr)rs[id]=Modify(rs[pre],m+1,r,ql,qr);
	return id;
}
int Query(int l,int r,int pos,int x){//查询某个版本的值
	if(l==r)return laz[x];
	int m=l+r>>1;
	return laz[x]+(pos<=m?Query(l,m,pos,ls[x]):Query(m+1,r,pos,rs[x]));
}
map <double,int> mp;
void Construct(){
	sort(p+1,p+cnt+1),sort(inf+1,inf+cinf+1); cnt=unique(p+1,p+cnt+1)-p-1;
	for(int i=1;i<=cnt;i++)mp[p[i]]=i;//离散化
	for(int i=1;i<=cs;i++){
		int l=mp[s[i].l],r=mp[s[i].r];
		if(i!=1) if(l<r)l++; else l--; if(l>r) swap(l,r);//注意区间边界 
		R[i]=Modify(R[i-1],1,cnt,l,r);
	}
}
int Binary_pos(query d){//二分区间位置
	int l=1,r=cs,dis=mp[d.c];
	while(l<r) {int m=l+r>>1,t=Query(1,cnt,dis,R[m]); if(t<d.f)l=m+1; else r=m;}
	return l;
}
double Binary_time(int pos,double dis){//二分时间
	section d=s[pos]; int pa=d.pa,pb=d.pb; bool down=d.l>d.r; double l=d.tl,r=d.tr;
	while(r-l>eps) {double m=(l+r)/2,dm=Calc(pa,pb,m); if(dm<dis&&down||dm>=dis&&!down)r=m; else l=m;}
	return (l+r)/2;
}
void Answer(){
	for(int i=1;i<=q;i++){
		int pos=lower_bound(inf+1,inf+cinf+1,c[i].c)-inf;
		if(pos<=cinf&&Equal(inf[pos],c[i].c)||pos>1&&Equal(inf[pos-1],c[i].c)) {puts("-2.33"); continue;}
		int tot=Query(1,cnt,mp[c[i].c],R[cs]);
		if(c[i].f>tot)puts("-4.66");//特判f>次数 
		else printf("%.8lf\n",Binary_time(Binary_pos(c[i]),c[i].c));
	}
}
int main() {Init(); Breakmove(); Construct(); Answer();}//后面三个主要函数的首字母重新排序后为 ABC（逃

接下来的部分是写好题解 $\sf{1\ Day}$ 后才有的。出题人经过一晚上的苦思冥想，发现了复杂度更优的解法。

$\sf{Subtask\ 4}$ ： $n\leq 8\times 10^4,q\leq 3\times 10^5$ 。

用两只 $\log$ 水过去的神仙，我请您抽烟。~~两只 $\log$ ，两只 $\log$ ，跑得快，跑得快。~~

同 $\sf{Subtask\ 3}$ 一样，我们将区间离散化后用主席树维护，然后用前缀和 $\sf{plus}$ 优化查找，就可以将查找部分的时间复杂度优化到单次 $\log n$ 。

总时间复杂度 $O(n\log n+q\log n+q\log D)$ ，别看 $n$ 只有 $8\times 10^4$ ，实际上区间的个数为 $4n=3.2\times 10^5$ ，点的个数可以达到惊人的 $8n+q=9.4\times 10^5$ ，所以常数还是很大的。实现起来也较麻烦，代码量约为 $\sf{4\sim 5k}$ 。

注意事项 & 卡常技巧：

注意空间限制。
浮点数的读入/输出很慢，建议手写 $\sf{IO}$ 。
离散化尽量不要用 $\sf{map}$ ，很慢。

~~千疮百孔的~~代码：

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pii pair <int,int>
namespace IO{//手写 IO
	char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	#define pc(x) (*O++=x)
	#define flush() fwrite(obuf,O-obuf,1,stdout)
	inline void read(int &x){
		bool sign=0; char s=gc(); x=0;
		while(!isdigit(s))sign|=s=='-',s=gc();
		while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc();
		if(sign)x=-x;
	}
	inline void read(double &x){
		bool sign=0; char s=gc(); x=0;
		while(!isdigit(s))sign|=s=='-',s=gc();
		while(isdigit(s))x=x*10+s-'0',s=gc();
		x+=(gc()-'0')*0.1,x+=(gc()-'0')*0.01;
		if(sign)x=-x;
	}
	inline void print(int x){
		if(x<10)pc(x+'0');
		else print(x/10),pc(x%10+'0');
	}
	inline void print(double x){
		if(x<0)pc('-'),x=-x;
		int d=x; print(d),x-=d;
		pc('.');
		for(int i=0;i<8;i++)x*=10.0,d=(int)x,pc(d+'0'),x-=d;
		pc('\n');
	}
	inline void print(string x){
		for(int i=0;i<x.size();i++)pc(x[i]);
		pc('\n');
	}
}
using namespace IO;
const int N=8e4+5,Q=3e5+5,P=1e6+5; const double eps=1e-9;
struct move {double x,y,t; bool operator < (const move &v) const {return t<v.t;} } a[N],b[N];
struct query {double c; int f;} c[Q];
struct section {double l,r,tl,tr; int pa,pb;} s[N<<2];
int n,m,q,cs,cnt,cinf;
double p[P],inf[P];
void Init(){
	read(n),read(m),read(q),read(a[0].x),read(a[0].y),read(b[0].x),read(b[0].y);
	for(int i=1;i<=n;i++)read(a[i].x),read(a[i].y),read(a[i].t);
	for(int i=1;i<=m;i++)read(b[i].x),read(b[i].y),read(b[i].t);
	for(int i=1;i<=q;i++)read(c[i].c),read(c[i].f),p[++cnt]=c[i].c;
}
bool Equal(double x,double y) {return abs(x-y)<=eps;}//判断两个数是否相等 
double Gap(double a,double b,double c,double d) {return sqrt((a-c)*(a-c)+(b-d)*(b-d));}//欧几里得距离公式
double Calc(int pa,int pb,double t){//求出某一时刻的距离
	double ra=(t-a[pa-1].t)/(a[pa].t-a[pa-1].t),rb=(t-b[pb-1].t)/(b[pb].t-b[pb-1].t);
	double xa=a[pa-1].x+(a[pa].x-a[pa-1].x)*ra,ya=a[pa-1].y+(a[pa].y-a[pa-1].y)*ra;
	double xb=b[pb-1].x+(b[pb].x-b[pb-1].x)*rb,yb=b[pb-1].y+(b[pb].y-b[pb-1].y)*rb;
	return Gap(xa,ya,xb,yb);
}
void Add(double x,double y,double l,double r,int pa,int pb) {s[++cs]={x,y,l,r,pa,pb},p[++cnt]=x,p[++cnt]=y;}//添加区间
void Breakmove(){//顾名思义，打破运动（求区间）
	int pa=1,pb=1;
	while(pa<=n&&pb<=m){
		double l=max(a[pa-1].t,b[pb-1].t),r=min(a[pa].t,b[pb].t),dl=Calc(pa,pb,l),dr=Calc(pa,pb,r);
		double m,d1,d2,L=l,R=r;
		int npa=pa+(r==a[pa].t),npb=pb+(r==b[pb].t);
		if(Equal(dl,dr)&&Equal(Calc(pa,pb,(l+r)/2),dr)) {inf[++cinf]=dl,pa=npa,pb=npb; continue;}//(1)，距离不变，infinity
		while(r-l>eps) {m=(l+r)/2,d1=Calc(pa,pb,m),d2=Calc(pa,pb,m+eps/3); d1<d2?r=m+eps/3:l=m;}//三分求最小值
		if(dl<d1||Equal(dl,d1)||Equal(d2,dr)||d2>dr)Add(dl,dr,L,R,pa,pb);//(2)(3)
		else {m=(l+r)/2,d1=Calc(pa,pb,m); Add(dl,d1,L,m,pa,pb),Add(d1,dr,m,R,pa,pb);}//(4)
		pa=npa,pb=npb;
	}
}
int node,R[N<<3];
struct data {int ls,rs,num;}d[P<<5];
int Modify(int pre,int l,int r,int pos,int v){
	int id=++node; d[id]=d[pre],d[id].num+=v;
	if(l==r)return id;
	int m=l+r>>1;
	if(pos<=m)d[id].ls=Modify(d[pre].ls,l,m,pos,v);
	else d[id].rs=Modify(d[pre].rs,m+1,r,pos,v);
	return id;
}
int Getpos(double x) {return lower_bound(p+1,p+cnt+1,x)-p;}
void Construct(){
	sort(p+1,p+cnt+1),sort(inf+1,inf+cinf+1); cnt=unique(p+1,p+cnt+1)-p-1;
	pii op[N<<3]; int cop=0,pos=1;
	for(int i=1;i<=cs;i++){
		int l=Getpos(s[i].l),r=Getpos(s[i].r);
		if(i!=1) if(l<r)l++; else l--; if(l>r) swap(l,r);//注意区间边界 
		op[++cop]={l,i},op[++cop]={r+1,-i};
	}
	sort(op+1,op+cop+1);
	for(int i=1;i<=cop;i++){
		while(pos<op[i].fi)R[pos+1]=R[pos],pos++;
		if(pos==cnt+1)break;
		R[pos]=Modify(R[pos],1,cs,abs(op[i].se),op[i].se>0?1:-1);
	}
}
int Query(int l,int r,int x,int k){//查找
	if(l==r)return l;
	int m=l+r>>1;
	return k<=d[d[x].ls].num?Query(l,m,d[x].ls,k):Query(m+1,r,d[x].rs,k-d[d[x].ls].num);
}
double Binary_time(int pos,double dis){//二分时间
	section d=s[pos]; int pa=d.pa,pb=d.pb; bool down=d.l>d.r; double l=d.tl,r=d.tr;
	while(r-l>eps) {double m=(l+r)/2,dm=Calc(pa,pb,m); if(dm<dis&&down||dm>=dis&&!down)r=m; else l=m;}
	return (l+r)/2;
}
void Answer(){
	for(int i=1;i<=q;i++){
		int pos=lower_bound(inf+1,inf+cinf+1,c[i].c)-inf;
		if(pos<=cinf&&Equal(inf[pos],c[i].c)||pos>1&&Equal(inf[pos-1],c[i].c)) {print("-2.33"); continue;}//特判infinity
		int p=Getpos(c[i].c);
		if(c[i].f>d[R[p]].num)print("-4.66");//特判f>次数
		else print(Binary_time(Query(1,cs,R[p],c[i].f),c[i].c));
	}
}
int main() {Init(); Breakmove(); Construct(); Answer(); flush();}//后面三个主要函数的首字母重新排序后为 ABC（逃

\sf{Conclusion}

本文中可能会有一些不太严谨的地方，请见谅。

希望大家能够通过这道题目对可持久化数组，标记永久化和前缀和优化有更进一步的理解，这也是我们出题的本意。

再次感谢 $\sf{\color{black}c\color{red}henxia25}$ （ $\sf{STO}$ ，他真的很强）！

$\sf{Upd\ on\ 2020.2.29:}$ 另外，感谢 $\color{gray}\sf{Alex\_Wei}$ （我自己）及时发现了复杂度更优的解法，才使得 $\sf{std}$ 不被吊打。

码字不易，点个赞呗 awa。另外，如果你发现了文章有错，及时告诉我哈，bye ~

ID

5169

时间

1000~2500ms

内存

128~256MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

「SWTR-4」Taking a Walk

信息

1 条题解

自动搬运

以下是正文

「SWTR-4」Taking a Walk

信息

还没有账户？

登录