自动搬运

查看原文

来自洛谷，原作者为

	myee 与其诺诺以顺，不若谔谔以昌 | AFO

搬运于2025-08-24 22:18:07，当前版本为作者最后更新于2023-06-14 21:32:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

很厉害的题目！不涉及什么高深的算法，一些细节却并不好想。

思路

我们设 $x_{i+1}=x_i+l_i,x_0=0$。

显然两个点 $u,v$ 要么走树上路径，要么走跨越该边的路径。

我们假设连边 $(s,t)$，满足 $s<t,u<v$。

则前者贡献是 $d_u+d_v+x_v-x_u$，后者贡献是 $d_u+d_v+|x_u-x_s|+|x_v-x_t|+c$。

考虑二分答案，判断答案是否 $\le w$。

也即，

$$\forall u<v,d_u+d_v+\min\{x_v-x_u,|x_u-x_s|+|x_v-x_t|+c\}\le w $$

也即

$$\forall u<v,(d_u-x_u)+(d_v+x_v)\le w\lor\begin{cases}(d_u+x_u)+(d_v+x_v)\le w+x_s+x_t-c\\(d_u+x_u)+(d_v-x_v)\le w+x_s-x_t-c\\(d_u-x_u)+(d_v+x_v)\le w-x_s+x_t-c\\(d_u-x_u)+(d_v-x_v)\le w-x_s-x_t-c\end{cases} $$

我们设 $A_p=d_p+x_p,B_p=d_p-x_p$，那么合法等价于

$$\forall u<v,B_u+A_v\le w\lor\begin{cases}A_u+A_v\le w+x_s+x_t-c\\A_u+B_v\le w+x_s-x_t-c\\B_u+A_v\le w-x_s+x_t-c\\B_u+B_v\le w-x_s-x_t-c\end{cases} $$

我们不妨对每个 $u<v\land B_u+A_v>w$ 算出后面四条限制的左式的最大值。

假设已经算出，我们就得到关于 $x_s$ 和 $x_t$ 的四条方程，也就得到 $x_t\pm x_s$ 的上下界，枚举下 $t$，可以顺带对 $s$ 的区间拿四个指针维护一下做到 $O(n)$。

于是考虑怎么算。直接对 $u<v$ 一维分治是单轮 $O(n\log n)$ 的，总复杂度 $O(n\log n\log(nv))$，较难通过。

考虑优化。

对于限制 $3,4$，考虑直接枚举 $v$。那么我们就是要得到前缀中每个 $B>w-A_v$ 的 $\max B$，直接维护前缀中最大 $B$，然后 check 其是否 $>w-A_v$ 即可。

限制 $1$ 可以通过枚举 $u$ 类似地实现。

最后考虑第 $2$ 条限制怎么求。

也即，我们现在需要求

$$\max_{u<v,B_u+A_v>w}\{A_u+B_v\}$$

这个看上去只能 $O(n\log n)$ 计算。

不过实际上由于本题性质，其可以做到 $O(n)$！

具体地，我们注意到随着 $u$ 的增长，必有 $A_u-B_u=2x_u$ 变大。

于是 $(A,B)$ 对只可能出现三种情况（把等于视作边界情况）：

• $A$ 增，$B$ 增。
• $A$ 增，$B$ 减。
• $A$ 减，$B$ 减。

拿一个单调栈维护一下。

如果你的 $A_u,B_u$ 均比上一个小，直接被暴打，因此可以当作不存在。顺带计算一下和上一项之间的贡献即可。

如果你的 $A_u,B_u$ 均比上一个大，直接暴打那个数，不妨在把上一个数弹栈的同时计算一下弹栈的两个数之间的贡献。

于是剩下的栈里总形如 $A$ 单调增 $B$ 单调减。

考虑建出栈之后，再解决栈内部的贡献。

这个直接双指针即可维护。

于是复杂度即为 $O(n)$。

最后由于要套一个二分答案，总复杂度 $O(n\log(nv))$。

Code

代码跑得很快。

以下是核心代码。

uint n;
llt X[1000005],A[1000005],B[1000005];
llt MaxPreB[1000005],MaxSufA[1000005],c;
std::vector<std::pair<llt,llt> >S,T;
bol check(llt w)
{
    llt x1=-1e18,x2=-1e18,x3=-1e18,x4=-1e18;
    for(uint i=0;i<n;i++)
    {
        if(A[i]+MaxPreB[i]>w)_max(x3,MaxPreB[i]+A[i]),_max(x4,MaxPreB[i]+B[i]);
        if(B[i]+MaxSufA[i]>w)_max(x1,MaxSufA[i]+A[i]);
    }
    for(auto s:T)if(s.first>w)_max(x2,s.second);
    for(uint i=1,j=0;i<S.size();i++)if(S[0].second+S[i].first>w)
    {
        while(j+1<i&&S[j+1].second+S[i].first>w)j++;
        _max(x2,S[j].first+S[i].second);
    }
    llt l_add=x1+c-w,r_add=w-x4-c,l_sub=x3+c-w,r_sub=w-x2-c;
    _max(l_add,X[1]),_max(l_sub,0ll),_min(r_add,X[n-1]+X[n-2]),_min(r_sub,X[n-1]);
    if(l_add>r_add||l_sub>r_sub)return false;
    for(uint i=0,a=n,b=n,c=0,d=0;i<n;i++)
    {
        while(a&&X[i]+X[a-1]>=l_add)a--;
        while(b&&X[i]+X[b-1]>r_add)b--;
        while(c<n&&X[c]+l_sub<=X[i])c++;
        while(d<n&&X[d]+r_sub<X[i])d++;
        if(std::max(a,d)<std::min(b,c))return true;
    }
    return false;
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    scanf("%u%lld",&n,&c);
    for(uint i=1;i<n;i++)scanf("%lld",X+i),X[i]+=X[i-1];
    for(uint i=0;i<n;i++)scanf("%lld",A+i),B[i]=A[i]-X[i],A[i]+=X[i];
    MaxPreB[0]=MaxSufA[0]=-1e18;
    for(uint i=1;i<n;i++)_max(MaxPreB[i]=MaxPreB[i-1],B[i-1]);
    for(uint i=n-1;i;i--)_max(MaxSufA[i-1]=MaxSufA[i],A[i]);
    S={{A[0],B[0]}};
    for(uint i=1;i<n;i++)
    {
        T.push_back({S.back().second+A[i],S.back().first+B[i]});
        if(S.back().first>=A[i])continue;
        while(S.size()&&S.back().second<=B[i])S.pop_back();
        S.push_back({A[i],B[i]});
    }
    llt l=0,r=X[n-1]+2000000000;
    while(l<r){llt mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}
    printf("%lld\n",l);
    return 0;
}