一个巧妙的想法是，把 w 补全成连续的函数，使其具有决策单调性。设 w'(x)，假设 w(x)=k，则让 k 级和 k+1 级中间的升级变成一次函数，即 w'(x)=k+\frac{x-B_k}{b_{k+1}}。w' 是连续且上凸的。这时我们有 DP f_i=\lfloor\max_{j=0}^{i-1}\{f_j+w'(j+1,i)\}\rfloor。这也有决策单调性，因为在四边形不等式中 f 是抵消的。
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n,m,c,p[500005];
long long a[500005],b[500005];
double f[500005];
double calc(int l,int r){
int k=upper_bound(b+1,b+m+1,a[r]-a[l])-b-1;
return k+1.0*(a[r]-a[l]-b[k])/(b[k+1]-b[k])-c;
}
void solve(int l,int r){
if(l==r){
f[l]=floor(f[l]);
return;
}
int mid=(l+r)>>1;
for(int i=p[l-1];i<=p[r];i++)if(f[i]+calc(i,mid)>f[mid])f[mid]=f[i]+calc(i,mid),p[mid]=i;
solve(l,mid);
for(int i=l;i<=mid;i++)if(f[i]+calc(i,r)>f[r])f[r]=f[i]+calc(i,r),p[r]=i;
solve(mid+1,r);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cin>>t;
while(t--){
cin>>n>>m>>c,b[m+1]=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=m;i++)cin>>b[i],b[i]+=b[i-1];
for(int i=1;i<=n;i++)f[i]=calc(0,i),p[i]=0;
solve(1,n),cout<<(long long)f[n]<<'\n';
}
return 0;
}
```
考虑优化，使用二分队列，瓶颈是最后一步，要求两个决策点 $j<i$ 的分界点。考虑实际上我们关心的是序列上的位置的 $w$，从 $w'$ 的分界点开始中间有一段区间按 $w$ 转移相同，我们可以任意分给
$i$ 或 $j$。我们可以求 $w$ 的分界点，也就是使 $i$ 恰好升级的位置，二分出升了 $k$ 级使 $a_j+B_{k+f_i-f_j}>a_i+B_k$。然后就可以再二分使从 $i$ 开始升了 $k$ 级的位置。
具体来说，$w'$ 的分界点是最小的 $x$ 使 $f_i+w'(x)>f_j+w'(x+B_i-B_j)$，$w$ 的分界点则是第一个满足 $f_i+w(x)>f_j+w(x+B_i-B_j)$ 的 $x$，最晚的分界点不能在 $f_i+w(x)>f_j+w(x+B_i-B_j)$ 且存在 $x=B_k-B_i$ 的第一个位置之后。我们取的分界点是 $w$ 的分界点后第一个序列上的位置。
复杂度 $O(m+n\log m)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n,m,c;
long long a[500005],b[500005];
double f[500005];
struct node{
int p,l,r;
}q[500005];
double calc(int l,int r){
int k=upper_bound(b+1,b+m+1,a[r]-a[l])-b-1;
return k+1.0*(a[r]-a[l]-b[k])/(b[k+1]-b[k])-c;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cin>>t;
while(t--){
cin>>n>>m>>c,b[m+1]=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=m;i++)cin>>b[i],b[i]+=b[i-1];
int bp=1,fp=1;
q[1]=(node){0,1,n};
for(int i=1;i<=n;i++){
while(q[bp].r<i)bp++;
f[i]=floor(f[q[bp].p]+calc(q[bp].p,i));
while(fp>bp&&f[i]+calc(i,q[fp].l)>f[q[fp].p]+calc(q[fp].p,q[fp].l))fp--;
int p;
if(f[i]<=f[q[fp].p])p=n+1;
else if(f[i]>f[q[fp].p]+m)p=i+1;
else{
int l=0,r=m-f[i]+f[q[fp].p]+1;
while(l<r){
int mid=(l+r)>>1;
if(a[q[fp].p]+b[(int)(mid+f[i]-f[q[fp].p])]>a[i]+b[mid])r=mid;
else l=mid+1;
}
p=lower_bound(a+1,a+n+1,a[i]+b[l])-a;
}
if(p<=n)q[fp].r=p-1,q[++fp]=(node){i,p,n};
}
cout<<(long long)f[n]<<'\n';
}
return 0;
}
```