神题orz……

我们考虑一下，当两个世界“同步”之时，哪种情况我们会选择传送，哪种情况则不。

显然，当这头牛的目的地比它现在的位置要高时，它应该尽量往下落速度慢的世界走，这样方便等待高处的目的地落下来，也因此只要与它同步的世界比它慢就应该传送；当这头牛的目的地比它现在的位置要低时，它应该尽量往下落速度快的世界走，以此来追赶它的目的地，也因此只要与它同步的世界比它快就应该传送。

我们可以证明，只要固定了目的地的高度关系（即高于出发点高度还是低于出发点高度），则无论时刻如何，每一个世界上的牛，都有着唯一的传送目标。

有些绕口吧？

我们不妨假设我们的目的地在出发点下方，则我们应该尽量往下落速度大的世界走。我们把目的地在出发点上方的情况称作UP类，而目的地在出发点下方的情况称作DW类。则我们以下只考虑DW类。

我们考虑对于每个世界，画出它的高度$h$与时间$t$的关系。（注意下文中“斜率”一词指的是倾斜程度，即越陡峭的线斜率越大，换句话说，是正常的斜率取绝对值后的结果）

一张典型的图可能会长这样：

则在一处交点处，就意味着发生了一次“同步”，也就意味着斜率小的直线可以在DW时传送到斜率大的直线上，而斜率大的直线可以在UP时传送到斜率小的直线上。

考虑对于具体的两条直线$f$和$g$。它们长成这样：

因为我们考虑的是DW情况，因此我们只考虑从$f$到$g$的情况。显然，只有当$g$是$f$出发后第一条遇见的大斜率直线时，$f$才会转移到$g$；否则，即之前存在一条大斜率直线，$f$就一定已经在那条直线上转移过去了。

这样看来，对于同一个$f$，这样的$g$应该是唯一的，因为$f$出发后遇到的第一条大斜率直线是唯一的。我们把这条直线$g$记作$dw_f$。这样子，如果我们已经找出了所有的$dw_f$，则对于询问，只需要不断地跳到$dw_f$，直到当前直线跑到了目的地的下面，即可。

但是，我们不能忽略的是，如果$f$不是从头开始的怎么办？换句话说，如果$f$不是出发点，它是从另一条直线，假设是$d$转移来的怎么办？这样子的话，（$dw_f$与$f$的交点）可能在（$f$与$d$的交点）前面，也就是说不能简单地跳到$dw_f$。

正常的情况是这样的图：

$d$在$A$处转移到$f$，然后$f$又在$B$处转移到$g$。

然后特殊的情形，就是$f$之前还遇到过一个大斜率直线$h$，因此$h$成为了$dw_f$，但是$h$实际上不能从$A$出发转移到，因为$h$与$f$的交点在$A$左边。因此正确的转移点就是$g$，而非我们之前口胡的那个“不断跳$dw_f$的算法”中的$dw_f$。

即这样的情形：

可以看到，$dw_f$是$h$，但是在$A$处时$f$却跳不到$h$（因为$f$与$h$的交点$C$在$A$前面）。

但是，细心的读者可能已经发现了，在这样的情况下，$dw_d$变成了$h$而不是原图的$f$！这就导致了实际上$d$早在$D$点处就已经转到了$h$，而不会像原来我们想象的那样到$A$点再转。

事实上，每个转移的目标，一定是$dw_f$，因为如果出现了之前相交过的情况，此时的直线$h$一定与$d$的交点在$A$前面。也因此，直接暴力跳$dw_f$的算法是正确的。

这只是DW的情况。类似的，UP的情况也可以通过我们预处理一个$up_f$数组出来进行转移。此处不再赘述。

我们可以写出这样的$n^2$做法（$n^2$预处理，$n^2$跳$dw/up$）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
int n,h[200100],up[200100],dw[200100],q[200100];
bool operator <=(const pii &u,const pii &v){
	return 1ll*u.x*v.y<=1ll*v.x*u.y;
}
bool operator >=(const pii &u,const pii &v){
	return 1ll*u.x*v.y>=1ll*v.x*u.y;
}
pii operator ~(pii u){
	if(u.x<=0)u.x*=-1,u.y*=-1;
	if(u.y<=0)return mp(0x3f3f3f3f,1);
	int tmp=__gcd(u.x,u.y);
	return mp(u.x/tmp,u.y/tmp);
}
pii cross(int x,int y){
	return ~mp(h[x]-h[y],x-y);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	for(int i=1;i<=n;i++)scanf("%d",&q[i]);
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
		if(h[j]<h[i])continue;
		if(!dw[i])dw[i]=j;
		else if(cross(i,j)<=cross(i,dw[i]))dw[i]=j;
	}
	for(int i=1;i<=n;i++)for(int j=i-1;j;j--){
		if(h[j]>h[i])continue;
		if(!up[i])up[i]=j;
		else if(cross(i,j)<=cross(i,up[i]))up[i]=j;
	}
	for(int i=1;i<=n;i++)printf("%d ",up[i]);puts("");
	for(int i=1;i<=n;i++)printf("%d ",dw[i]);puts("");
	for(int i=1;i<=n;i++){
		int j=i;
		if(h[q[i]]>h[i])while(up[j]&&cross(j,q[i])>=cross(up[j],q[i]))j=up[j];
		else while(dw[j]&&cross(j,q[i])>=cross(dw[j],q[i]))j=dw[j];
		pii p=cross(j,q[i]);
		if(p==mp(0x3f3f3f3f,1))puts("-1");
		else printf("%d/%d\n",p.first,p.second);
	}
	return 0;
}

期望得分$35\%$。

我们考虑优化。

如果我们画出每个位置的$dw_f$的话，会发现实际上构成了一个（一堆）凸包：

即这样：

凸包可以通过单调队列预处理出来。复杂度$O(n)$。但是初始化时需要进行排序，因此是$O(n\log n)$的。

代码（实际上还是$O(n^2)$的，只不过跳$dw$时的深度可能比较小致使能通过$84\%$）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
int n,h[200100],up[200100],dw[200100],q[200100],stk[200100],tp,ord[200100];
bool operator <=(const pii &u,const pii &v){
	return 1ll*u.x*v.y<=1ll*v.x*u.y;
}
bool operator >=(const pii &u,const pii &v){
	return 1ll*u.x*v.y>=1ll*v.x*u.y;
}
pii operator ~(pii u){
	if(u.x<=0)u.x*=-1,u.y*=-1;
	if(u.y<=0)return mp(0x3f3f3f3f,1);
	int tmp=__gcd(u.x,u.y);
	return mp(u.x/tmp,u.y/tmp);
}
pii cross(int x,int y){
	return ~mp(h[x]-h[y],x-y);
}
bool cmp(int x,int y){
	return h[x]<h[y];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]),ord[i]=i;
	for(int i=1;i<=n;i++)scanf("%d",&q[i]);
	sort(ord+1,ord+n+1,cmp);
	tp=0;
	for(int i=n;i;i--){
		int j=ord[i];
		while((tp&&cross(j,stk[tp])==mp(0x3f3f3f3f,1))||(tp>=2&&cross(j,stk[tp-1])<=cross(j,stk[tp])))tp--;
		dw[j]=stk[tp],stk[++tp]=j;
	}
	tp=0;
	for(int i=1;i<=n;i++){
		int j=ord[i];
		while((tp&&cross(j,stk[tp])==mp(0x3f3f3f3f,1))||(tp>=2&&cross(j,stk[tp-1])<=cross(j,stk[tp])))tp--;
		up[j]=stk[tp],stk[++tp]=j;
	}
//	for(int i=1;i<=n;i++)printf("%d ",up[i]);puts("");
//	for(int i=1;i<=n;i++)printf("%d ",dw[i]);puts("");
	for(int i=1;i<=n;i++){
		int j=i;
		if(h[q[i]]>h[i])while(up[j]&&cross(j,q[i])>=cross(up[j],q[i]))j=up[j];
		else while(dw[j]&&cross(j,q[i])>=cross(dw[j],q[i]))j=dw[j];
		pii p=cross(j,q[i]);
		if(p==mp(0x3f3f3f3f,1))puts("-1");
		else printf("%d/%d\n",p.first,p.second);
	}
	return 0;
}

发现所有的$dw/up$一定构成一棵树的结构。因此我们只需要建出这棵树，然后在上面树上倍增就可以在$\log n$时间内找到在目的地直线上方的最后一条直线。

总复杂度$O(n\log n)$。期望得分$100\%$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
int n,h[200100],up[200100][20],dw[200100][20],q[200100],stk[200100],tp,ord[200100];
bool operator <=(const pii &u,const pii &v){
	return 1ll*u.x*v.y<=1ll*v.x*u.y;
}
bool operator >=(const pii &u,const pii &v){
	return 1ll*u.x*v.y>=1ll*v.x*u.y;
}
pii operator ~(pii u){
	if(u.x<=0)u.x*=-1,u.y*=-1;
	if(u.y<=0)return mp(0x3f3f3f3f,1);
	int tmp=__gcd(u.x,u.y);
	return mp(u.x/tmp,u.y/tmp);
}
pii cross(int x,int y){
	return ~mp(h[x]-h[y],x-y);
}
bool cmp(int x,int y){
	return h[x]<h[y];
}
void print(pii p){
	if(p==mp(0x3f3f3f3f,1))puts("-1");
	else printf("%d/%d\n",p.first,p.second);
}
bool upche(int x,int y){
	if(!up[x][0])return false;
	pii u=cross(up[x][0],x);
	return 1ll*(h[x]-h[y])*u.y<=1ll*u.x*(x-y);
}
bool dwche(int x,int y){
	if(!dw[x][0])return false;
	pii u=cross(dw[x][0],x);
	return 1ll*(h[x]-h[y])*u.y>=1ll*u.x*(x-y);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]),ord[i]=i;
	for(int i=1;i<=n;i++)scanf("%d",&q[i]);
	sort(ord+1,ord+n+1,cmp);
	tp=0;
	for(int i=n;i;i--){
		int j=ord[i];
		while((tp&&cross(j,stk[tp])==mp(0x3f3f3f3f,1))||(tp>=2&&cross(j,stk[tp-1])<=cross(j,stk[tp])))tp--;
		dw[j][0]=stk[tp],stk[++tp]=j;
	}
	for(int j=1;j<19;j++)for(int i=1;i<=n;i++)dw[i][j]=dw[dw[i][j-1]][j-1];
	tp=0;
	for(int i=1;i<=n;i++){
		int j=ord[i];
		while((tp&&cross(j,stk[tp])==mp(0x3f3f3f3f,1))||(tp>=2&&cross(j,stk[tp-1])<=cross(j,stk[tp])))tp--;
		up[j][0]=stk[tp],stk[++tp]=j;
	}
	for(int j=1;j<19;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
//	for(int i=1;i<=n;i++)printf("%d ",up[i][0]);puts("");
//	for(int i=1;i<=n;i++)printf("%d ",dw[i][0]);puts("");
	for(int i=1;i<=n;i++){
		int j=i;
		if(h[q[i]]>h[i]&&upche(i,q[i])){
			for(int k=18;k>=0;k--)if(up[j][k]&&upche(up[j][k],q[i]))j=up[j][k];
			j=up[j][0];
		}
		if(h[q[i]]<h[i]&&dwche(i,q[i])){
			for(int k=18;k>=0;k--)if(dw[j][k]&&dwche(dw[j][k],q[i]))j=dw[j][k];
			j=dw[j][0];
		}
		print(cross(j,q[i]));
	}
	return 0;
}