题解：P9521 [JOISC 2022] 京都观光

Mirasycle · 2025-02-17 08:34:23 · 题解

考虑 (l,x)\to(r,y) 的路径可以 (l,x)\to (r,x)\to (r,y)，也可以 (l,x)\to (l,y)\to (r,y)。

前者的代价是 b_x(r-l)+a_r(y-x)，后者的代价是 a_l(y-x)+b_y(r-l)。前者比后者更优需要满足

可以发现这可以放到两个凸包上求解。单调栈建立对于 a,b 的凸包之后，每次选择斜率写的一边走。由于上述式子可以放到到任意局部，所以这是对的。

其实本质就是对于两个凸包进行闵可夫斯基和。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int n,m,a[maxn],b[maxn]; ll ans=0;
int sta[maxn],stb[maxn],ta,tb;
bool chk(int x1,int y1,int x2,int y2){ return 1ll*y1*x2<=1ll*y2*x1; }
bool cmpa(int x,int y,int z){ return chk(x-y,a[x]-a[y],y-z,a[y]-a[z]); }
bool cmpb(int x,int y,int z){ return chk(x-y,b[x]-b[y],y-z,b[y]-b[z]); }
bool cmpab(int w,int x,int y,int z){ return chk(w-x,a[w]-a[x],y-z,b[y]-b[z]); }
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sta[ta=1]=1; stb[tb=1]=1;
    for(int i=2;i<=n;i++){
        while(ta>1&&cmpa(i,sta[ta],sta[ta-1])) ta--;
        sta[++ta]=i;
    }
    for(int i=2;i<=m;i++){
        while(tb>1&&cmpb(i,stb[tb],stb[tb-1])) tb--;
        stb[++tb]=i;
    }
    int x=1,y=1;
    while(x<ta||y<tb){
        if(x==ta){
            ans+=1ll*(m-stb[y])*a[sta[x]];
            break;
        }
        if(y==tb){
            ans+=1ll*(n-sta[x])*b[stb[y]];
            break;
        }
        if(cmpab(sta[x+1],sta[x],stb[y+1],stb[y])){
            ans+=1ll*(sta[x+1]-sta[x])*b[stb[y]];
            x++;
        }else{
            ans+=1ll*(stb[y+1]-stb[y])*a[sta[x]];
            y++; 
        }
    }
    cout<<ans;
    return 0;
}