P9521

SoyTony · 2023-08-24 16:13:25 · 题解

考虑行 x<y<z，列 l<r，那么有三种移动方式：

经过 y 的条件时后者小于前面两个式子，移项整理得到：

因此对 a 维护一下下凸壳，b 同理。

现在就只考虑是向下或向右了，把前两个式子比较，有：

因此每次会选择沿斜率较小的方向移动，维护两个指针分别在两个凸包上移动即可。

int n,m;
int a[maxn],b[maxn];

inline bool check_slope_a(int x,int y,int z){
    ll lhs=1ll*(a[y]-a[x])*(z-y),rhs=1ll*(a[z]-a[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_b(int x,int y,int z){
    ll lhs=1ll*(b[y]-b[x])*(z-y),rhs=1ll*(b[z]-b[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_ab(int x,int y,int l,int r){
    ll lhs=1ll*(a[y]-a[x])*(r-l),rhs=1ll*(b[r]-b[l])*(y-x);
    return lhs<rhs;
}

int sta[maxn],topa;
int stb[maxn],topb;

ll ans;

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i) b[i]=read();
    sta[++topa]=1;
    for(int i=2;i<=n;++i){
        while(topa>1&&check_slope_a(sta[topa-1],sta[topa],i)) --topa;
        sta[++topa]=i;
    }
    stb[++topb]=1;
    for(int i=2;i<=m;++i){
        while(topb>1&&check_slope_b(stb[topb-1],stb[topb],i)) --topb;
        stb[++topb]=i;
    }
    int i=1,j=1;
    while(i<topa||j<topb){
        if(i==topa){
            ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
            ++j;
        }
        else if(j==topb){
            ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
            ++i;
        }
        else{
            if(check_slope_ab(sta[i],sta[i+1],stb[j],stb[j+1])){
                ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
                ++i;
            }
            else{
                ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
                ++j;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}