自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:16:30，当前版本为作者最后更新于2023-05-02 14:49:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

首先能想到一个正确但暴力的贪心，即如果 $A_{Q_i}<A_i$ 则要尽量快地往下走（碰到编号比当前大的世界就要传送），否则要尽量慢地向下走。例如下图中直线表示样例中每个世界纵坐标与时间的关系，从世界 $1$ 出发的牛会按照紫色波浪线每次往编号大的世界走。

下面考虑如何快速维护这个过程，因为两种情况是对称的，故只考虑前者。

容易发现从世界 $i$ 出发所到达的地方是一个凸包，并且 $A_j<A_i$ 的世界显然没有用，要么没交点要么走得慢，所以是所有 $A_j\geq A_i$ 的世界所构成的凸包。这提示我们只需要按照 $A_i$ 从大到小的顺序插入直线维护凸包，插完点 $i$ 时的凸包就满足该处询问所需。因为截距是单调的，所以只需要单调栈维护即可，此处时间复杂度 $O(n)$。

再考虑询问，不是很懂题解里怎么都要根据凸包建树倍增，既然你都维护出凸包了为什么不直接在上面二分呢？于是只需使用二分，时间复杂度 $O(n\log n)$，可以通过本题，且常数和码量都很小。

代码

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long

int n,a[100005],q[100005],bh[100005],stk[100005],top,ansz[100005],ansm[100005];
bool cmp(int x,int y) {return a[x]>a[y];}
bool check(int x,int y,int k) {return (a[x]-a[k])*(y-k)<(a[y]-a[k])*(x-k);}
void ins(int x,bool zt)
{
	while(top&&(zt^(x>stk[top]))||top>1&&check(stk[top-1],stk[top],x)) top--; stk[++top]=x;
	if(zt^(a[q[x]]<a[x]))
	{
		if(zt^(q[x]>stk[1])) return; int l=2,r=top;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if((zt^(q[x]<stk[mid]))&&check(stk[mid],stk[mid-1],q[x])) l=mid+1;
			else r=mid-1;
		}
		ansz[x]=a[stk[r]]-a[q[x]]; ansm[x]=stk[r]-q[x]; int gcdd=__gcd(ansz[x],ansm[x]);
		ansz[x]/=gcdd; ansm[x]/=gcdd;
	}
}

signed main()
{
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	cin>>n; for(int i=1;i<=n;i++) cin>>a[i],bh[i]=i;
	for(int i=1;i<=n;i++) cin>>q[i]; sort(bh+1,bh+n+1,cmp);
	for(int i=1;i<=n;i++) ins(bh[i],0); top=0; //a[q[i]]<a[i]
	for(int i=n;i>=1;i--) ins(bh[i],1);//a[q[i]]>a[i]
	for(int i=1;i<=n;i++) if(!ansz[i]) cout<<"-1\n"; else cout<<ansz[i]<<"/"<<ansm[i]<<"\n";
}