P6010 题解

honglan0301 · 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";
}