「SWTR-04」F Taking a Walk
Alex_Wei
·
·
题解
\mathsf{Preface}
题面传送门。
感谢 @\color{black}\sf{c\color{red}henxia25} 在验题时的错误 idea 帮助我想到了复杂度更优的解法。
\mathsf{Solution}
核心思想：“切割”。切割时间，使得每个时间段内小 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}$。
代码（为了验题写的暴力）：
```cpp
#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}$](https://www.luogu.com.cn/user/138400) 的错误 $\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}$。
```cpp
#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}$，很慢。
~~千疮百孔的~~代码：
```cpp
#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}$](https://www.luogu.com.cn/user/138400)（$\sf{STO}$，他真的很强）！
$\sf{Upd\ on\ 2020.2.29:}$ 另外，感谢 [$\color{gray}\sf{Alex\_Wei}$](https://www.luogu.com.cn/user/123294)（我自己）及时发现了复杂度更优的解法，才使得 $\sf{std}$ 不被吊打。
码字不易，点个赞呗 awa。另外，如果你发现了文章有错，及时告诉我哈，bye ~