sequence
题目传送门
解题思路
用单调栈求出每个a[i]作为最小值的最大范围。对于每个a[i],我们都要乘以一个以a[i]为区间内最小值的对应的b的区间和s，如果a[i] > 0，则s要尽量大，如果a[i] < 0,则s要尽量小。因为一段区间的和可以利用前缀和c[]相减求出，而以a[i]为最小值的区间和为：c[i~r] - c[l-1~i-1]。 所以用b[i]的前缀和建立线段树，维护其最大最小值。要求最大的s，即为求i~r内的最大前缀和与l-1~i-1范围内的最小前缀和。求最小的s同理。
代码如下
#include <bits/stdc++.h>
#define INF 5223372036854775807LL
using namespace std;
typedef long long ll;inline int read(){int res = 0, w = 0; char ch = 0;while(!isdigit(ch)){w |= ch == '-', ch = getchar();}while(isdigit(ch)){res = (res << 3) + (res << 1) + (ch ^ 48);ch = getchar();}return w ? -res : res;
}const int N = 3000005;ll a[N], b[N];
ll c[N];
struct T{int l, r;ll maxx, minn;
}tree[N<<2];void build(int k, int l, int r)
{tree[k].l = l;tree[k].r = r;if(l == r){tree[k].maxx = tree[k].minn = c[l];return;}int mid = (l + r) / 2;build(2*k, l, mid);build(2*k+1, mid + 1, r);tree[k].maxx = max(tree[2*k].maxx, tree[2*k+1].maxx);tree[k].minn = min(tree[2*k].minn, tree[2*k+1].minn);
}ll query_minn(int k, int l, int r)
{if(tree[k].l >= l && tree[k].r <= r)return tree[k].minn;int mid = (tree[k].l + tree[k].r) / 2;ll m1 = INF, m2 = INF;if(l <= mid)m1 = query_minn(2*k, l, r);if(r > mid)m2 = query_minn(2*k+1, l, r);return min(m1, m2);
}ll query_maxx(int k, int l, int r)
{if(tree[k].l >= l && tree[k].r <= r)return tree[k].maxx;int mid = (tree[k].l + tree[k].r) / 2;ll m1 = -INF, m2 = -INF;if(l <= mid)m1 = query_maxx(2*k, l, r);if(r > mid)m2 = query_maxx(2*k+1, l, r);return max(m1, m2);
}int l[N], r[N];
int dq[N];int main()
{int n;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 ++)c[i] = c[i - 1] + b[i];build(1, 1, n);int ql, qr;ql = qr = 0;for(int i = 1; i <= n; i ++){while(ql != qr && a[dq[qr - 1]] >= a[i])qr --;if(ql != qr)l[i] = dq[qr - 1] + 1;elsel[i] = 1;dq[qr++] = i;}ql = qr = 0;for(int i = n; i >= 1; i --){while(ql != qr && a[dq[qr - 1]] >= a[i])qr --;if(ql != qr)r[i] = dq[qr - 1] - 1;elser[i] = n;dq[qr++] = i;}ll ans = -INF;for(int i = 1; i <= n; i ++){if(a[i] < 0){ans = max(ans, a[i] * (query_minn(1, i, r[i]) - query_maxx(1, l[i] - 1, i - 1)));}else if(a[i] > 0){ans = max(ans, a[i] * (query_maxx(1, i, r[i]) - query_minn(1, l[i] - 1, i - 1)));}elseans = max(ans, 0LL);}cout << ans << endl;return 0;
}