题意

一列\(n\)个点,给定一个特殊的图,有两种边\(E(1,i)\)\(E(i-1,i)\),多个询问,每次给一个\(d\),求所有路径长度加上\(d\)后1到\(n\)的最短路。

分析

  • 首先这图很特殊,大胆猜测不是图论。
  • 1到\(n\)的最短路包括\(p_i\),即1直接到\(i\)的距离,\(i\)作为中转点,加上\(dis_{i,n}\),即\(i\)一直往后走到\(n\)的距离,而该路径的边数就是\(1+n-i\),因此对于每个询问\(d\),该路径的长度就是\(p_i+dis_{i,n}+d*(1+n-i)\)
  • 因此转化为另一个问题,有\(n\)个二元组\((a_i,b_i)\),对于每个\(d\),求\(min _{i=1}^{n}(a_i+d*b_i)\)
  • 观察这个二元组的形式,可以再转化为一个几何问题,有\(n\)条直线,斜率为\(b_i\),截距为\(a_i\),对于每个询问的横坐标\(d\),求最小的\(y\)值。
  • 画个图观察,可以知道,我们所需要的就是这些直线下部的折线所围成的一个上凸包。
  • 考虑用单调栈来维护,首先对直线按截距排序,枚举直线,如果斜率比上一条直线大,直接跳过,因为这条直线肯定在凸包的外部,没有贡献。
  • 单调栈维护要考虑栈顶元素什么情况下要去掉,假设当前直线为\(c\),栈顶直线为\(b\),栈顶下一个直线为\(a\),画图可以看出,当\(c\)\(b\)的交点横坐标小于\(b\)\(a\)的交点横坐标时,直线\(b\)就是无效的,处于凸包外部,因此出栈。
  • 维护完单调栈后,对询问\(d\)进行排序,显然对于小的\(d\),能使其最优的直线,对于大的\(d\)应该也是优的,且可以继续往下找可以更优的直线,因此只要从小到大排序后扫一遍单调栈即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const double eps=1e-8;
int t,n,que;
ll p[N],dis[N];
struct Line{
    ll k,b;
    bool operator <(const Line& rhs)const{
        return b<rhs.b;
    }
}ls[N],q[N*2];
int sgn(double x){
    if(fabs(x)<eps){
        return 0;
    }
    if(x<0){
        return -1;
    }else{
        return 1;
    }
}
struct Q{
    int id,d;
    ll ans;
    bool operator <(const Q &rhs)const{
        return d<rhs.d;
    }
}qs[N];
bool cmp(Q a,Q b){
    return a.id<b.id;
}
//两线交点横坐标
double xp(Line a,Line b){
    return (b.b-a.b)*1.0/(a.k-b.k);
}
int main(){
//    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&que);
        p[1]=0;
        for(int i=2;i<=n;i++){
            scanf("%lld",&p[i]);
        }
        dis[1]=p[2];
        for(int i=2;i<n;i++){
            scanf("%lld",&dis[i]);
        }
        dis[n]=0;
        for(int i=n-1;i>=1;i--){
            dis[i]+=dis[i+1];
        }
        for(int i=1;i<=que;i++){
            scanf("%d",&qs[i].d);
            qs[i].id=i;
            qs[i].ans=0;
        }
        //构造出n条直线并按截距排序
        ls[1]={n-1,p[1]+dis[1]};
        for(int i=2;i<=n;i++){
            ls[i]={1+n-i,p[i]+dis[i]};
        }
        sort(ls+1,ls+n);
        //维护一个斜率递增的单调队列
        int l=1,r=0;
        q[r++]=ls[2];
        for(int i=3;i<=n;i++){
            if(ls[i].k>ls[i-1].k){
                //斜率截距都比上一个大,凸包外部
                continue;
            }
            while(r-l+1>=2 && sgn(xp(ls[i],q[r-1])-xp(q[r-1],q[r-2])<=0)){
                r--;
            }
            q[r++]=ls[i];
        }
        sort(qs+1,qs+1+que);
        //越大的增值d乘越大的斜率更优,扫一遍,上一个(小d)能乘的斜率,这一个(大d)肯定也优,但可以更优
        int j=0;
        for(int i=1;i<=que;i++){
            while(j<r-1 && qs[i].d*q[j].k+q[j].b>qs[i].d*q[j+1].k+q[j+1].b){
                j++;
            }
            qs[i].ans=qs[i].d*q[j].k+q[j].b;
        }
        sort(qs+1,qs+1+que,cmp);
        for(int i=1;i<=que;i++){
            printf("%lld%c",qs[i].ans,i==que?'\n':' ');
        }
    }
    return 0;
}