牛客多校第四场 C

题意：

题目意思很简单，就是给你俩个序列a和b。

输出最大的min(al....r)*sum(bl....r),这里min是区间的最小是，sum是区间和

题解：

首先处理a数组中的最小值，用单调栈得出每一个位置为最小值对应的左端点和右端点

考虑如何求最大值，

如果a[i]<0 那么就要最小化sum(b)，

如果a[i]>0 那么就要最大化sum(b),

现在问题转移到了求最大的sum(b)和最小的sum(b)在区间[l,r]上

记录b的前缀和，用线段树存放前缀和，求区间[l,r]的最大值和最小值，

最大化sum(b)就要用最大值-最小值

最小化sum(b)就要用最小值-最大值

代码：

#include<bits/stdc++.h>
//#include<vector>
//#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define ms(a,b) memset(a, b, sizeof(a))
typedef long long ll;
const int MAXN = 3e6 + 50;
const int INF = 0x3f3f3f3f;
const ll  LINF = 0x3f3f3f3f3f3f3f3f;
template <class T>
inline bool scan_d(T &ret) {
  char c; int sgn;
  if (c = getchar(), c == EOF) return 0;
  while (c != '-' && (c<'0' || c>'9')) c = getchar();
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
  ret *= sgn;
  return 1;
}
int t, n;
int a[MAXN];
int b[MAXN];
ll sum[MAXN];
struct node{
  ll mi, mx;
}Tree[MAXN*4];
int l[MAXN], r[MAXN];
void built(int rt, int l, int r){
  if(l==r){
      Tree[rt].mi = Tree[rt].mx = sum[l];
      return;
  }

  built(rt<<1, l, (l+r)/2);
  built(rt<<1|1, (l+r)/2+1, r);

  Tree[rt].mx = max(Tree[rt<<1].mx, Tree[rt<<1|1].mx);
  Tree[rt].mi = min(Tree[rt<<1].mi, Tree[rt<<1|1].mi);
}
ll querymi(int rt, int l, int r, int a, int b){
  if(b < l || a > r) return LINF;
  if(a <= l && r <= b){
      return Tree[rt].mi;
  }else{
      int mid = (l+r)/2;
      ll lans = LINF, rans = LINF;
      if(mid >= a)  lans = querymi(rt<<1, l, mid, a, b);
      if(mid+1 <= b) rans = querymi(rt<<1|1, mid+1, r, a, b);
      return min(lans, rans);
  }
}
ll querymx(int rt, int l, int r, int a, int b){
  if(b < l || a > r) return -LINF;
  if(a <= l && r <= b){
      return Tree[rt].mx;
  }else{
      int mid = (l+r)/2;
      ll lans = -LINF, rans = -LINF;
      if(mid >= a) lans = querymx(rt<<1, l, mid, a, b);
      if(mid+1 <= b) rans = querymx(rt<<1|1, mid+1, r, a, b);
      return max(lans, rans);
  }
}
int main() {
  scanf("%d", &n);
  rep(i, 1, n){
      scan_d(a[i]);
  }
  rep(i, 1, n){
      scan_d(b[i]);
      sum[i] = sum[i-1]+b[i];
  }
  built(1, 0, n);
  stack<int> sta;
  per(i, n, 1){
      while(!sta.empty() && a[sta.top()] >= a[i]){
          sta.pop();
      }
      if(sta.empty()){
          r[i] = n+1;
      }else{
          r[i] = sta.top();
      }
      sta.push(i);
  }
  while(!sta.empty()) sta.pop();
  rep(i, 1, n){
      while(!sta.empty() && a[sta.top()] >= a[i]){
          sta.pop();
      }
      if(sta.empty()){
          l[i] = 0;
      }else{
          l[i] = sta.top();
      }
      sta.push(i);
  }

  long long ans = -LINF;
  rep(i, 1, n){
      ll y1, y2;
      if(a[i] > 0){
          y1 = querymi(1, 0, n, l[i], i-1);
          y2 = querymx(1, 0, n, i, r[i]-1);

      }
      else{
          y1 = querymx(1, 0, n, l[i], i-1);
          y2 = querymi(1, 0, n, i, r[i]-1);
      }
      ans = max(ans, (y2 - y1) * a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}