题目链接：nowcoder多校4-sequence

题意：

给定两个数组a和b，然后询问一个区间最大值，区间最大值的定义为该区间内a数组中的最小值与b数组中区间和的乘积。

题解：

单调栈+线段树。

对于a[i]，求出a[i]之前第一个比a[i]小的a[l]，a[i]之后第一个比a[i]小的a[r]，所以在区间[l+1,r-1]中的最小值即为a[i]。

然后对于数组b，记录其前缀和，然后对于a[i]，求出区间[i,r-1]中的最大值与区间[l,i-1]中的最小值，作差后与a[i]相乘即可。区间最大值最小值查询可使用线段树/RMQ等。

参考代码：

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 3e6 + 6;
const ll inf = 0x3f3f3f3f;
int n;
int a[MAXN], b[MAXN], lm[MAXN], rm[MAXN];
ll sum[MAXN];
ll maxv[MAXN << 2], minv[MAXN << 2];
void pushup(int rt)
{
    minv[rt] = min(minv[rt << 1], minv[rt << 1 | 1]);
    maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        minv[rt] = maxv[rt] = sum[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
ll query_max(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return maxv[rt];
    ll res = -inf;
    int mid = (l + r) / 2;
    if (L <= mid)
        res = max(res, query_max(L, R, l, mid, rt << 1));
    if (R > mid)
        res = max(res, query_max(L, R, mid + 1, r, rt << 1 | 1));
    return res;
}
ll query_min(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return minv[rt];
    ll res = inf;
    int mid = (l + r) / 2;
    if (L <= mid)
        res = min(res, query_min(L, R, l, mid, rt << 1));
    if (R > mid)
        res = min(res, query_min(L, R, mid + 1, r, rt << 1 | 1));
    return res;
}
struct node
{
    int num, id;
};
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]), sum[i] = sum[i - 1] + b[i];
    build(0, n, 1);
    stack<node> sta;
    a[0] = a[n + 1] = -inf;
    for (int i = 0; i <= n; i++)
    {
        node now;
        now.num = a[i], now.id = i;
        if (sta.empty())
        {
            sta.push(now);
            lm[i] = i - 1;
            continue;
        }
        while (!sta.empty())
        {
            if (a[i] <= sta.top().num)
                sta.pop();
            else
                break;
        }
        if (sta.empty())
        {
            sta.push(now);
            lm[i] = i - 1;
        }
        else
        {
            lm[i] = sta.top().id;
            sta.push(now);
        }
    }
    while (!sta.empty())
        sta.pop();
    for (int i = n + 1; i >= 1; i--)
    {
        node now;
        now.num = a[i], now.id = i;
        if (sta.empty())
        {
            sta.push(now);
            rm[i] = i + 1;
            continue;
        }
        while (!sta.empty())
        {
            if (a[i] <= sta.top().num)
                sta.pop();
            else
                break;
        }
        if (sta.empty())
        {
            sta.push(now);
            rm[i] = i + 1;
        }
        else
        {
            rm[i] = sta.top().id;
            sta.push(now);
        }
    }
    ll ans = -inf;
    for (int i = 1; i <= n; i++)
    {
        ll temp, minn, maxn;
        if (a[i] >= 0)
        {
            maxn = query_max(i, rm[i] - 1, 0, n, 1);
            minn = query_min(lm[i], i - 1, 0, n, 1);
            temp = maxn - minn;
        }
        else
        {
            maxn = query_max(lm[i], i - 1, 0, n, 1);
            minn = query_min(i, rm[i] - 1, 0, n, 1);
            temp = minn - maxn;
        }
        ans = max(ans, temp * (ll)a[i]);
    }
    printf("%lld\n", ans);
    return 0;
}