单调栈 + 线段树

先单调栈预处理a中每一个数覆盖的范围，然后用线段树维护b的前缀和，在选i的范围内查询区间值。

讨论一下a的正负性

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define FAST_IO ios::sync_with_stdio(false)using namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 4000005;int n, a[N], b[N], L[N], R[N];LL mx[N<<2], mn[N<<2], sum[N];void calc(){    stack
      
        st;    a[0] = a[n + 1] = -INF;    st.push(0);    for(int i = 1; i <= n; i ++){        while(!st.empty() && a[st.top()] >= a[i]) st.pop();        L[i] = st.top();        st.push(i);    }    while(!st.empty()) st.pop();    st.push(n + 1);    for(int i = n; i >= 1; i --){        while(!st.empty() && a[st.top()] >= a[i]) st.pop();        R[i] = st.top();        st.push(i);    }}void push_up(int rt){    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);    mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);}void buildTree(int rt, int l, int r){    if(l == r){        mx[rt] = mn[rt] = sum[l];        return;    }    int mid = (l + r) >> 1;    buildTree(rt << 1, l, mid);    buildTree(rt << 1 | 1, mid + 1, r);    push_up(rt);}LL queryMax(int rt, int l, int r, int ql, int qr){    if(l == ql && r == qr){        return mx[rt];    }    int mid = (l + r) >> 1;    if(qr <= mid) return queryMax(rt << 1, l, mid, ql, qr);    else if(ql > mid) return queryMax(rt << 1 | 1, mid + 1, r, ql, qr);    else return max(queryMax(rt << 1, l, mid, ql, mid), queryMax(rt << 1 | 1, mid + 1, r, mid + 1, qr));}LL queryMin(int rt, int l, int r, int ql, int qr){    if(l == ql && r == qr){        return mn[rt];    }    int mid = (l + r) >> 1;    if(qr <= mid) return queryMin(rt << 1, l, mid, ql, qr);    else if(ql > mid) return queryMin(rt << 1 | 1, mid + 1, r, ql, qr);    else return min(queryMin(rt << 1, l, mid, ql, mid), queryMin(rt << 1 | 1, mid + 1, r, mid + 1, qr));}int main(){    n = read();    for(int i = 1; i <= n; i ++) a[i] = read();    for(int i = 1; i <= n; i ++) b[i] = read();    for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + b[i];    calc();    buildTree(1, 0, n);    LL ans = 0;    for(int i = 1; i <= n; i ++){        int pl = L[i], pr = i - 1;        int sl = i, sr = R[i] - 1;        if(a[i] < 0){            ans = max(ans, 1LL * a[i] * (queryMin(1, 0, n, sl, sr) - queryMax(1, 0, n, pl, pr)));        }        else if(a[i] > 0){            ans = max(ans, 1LL * a[i] * (queryMax(1, 0, n, sl, sr) - queryMin(1, 0, n, pl, pr)));        }    }    printf("%lld\n", ans);    return 0;}