6167

myee · 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。

也即，

也即

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

我们不妨对每个 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 条限制怎么求。

也即，我们现在需要求

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

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

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

于是 (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;
}