题意
一列(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?'
':' ');
}
}
return 0;
}