https://ac.nowcoder.com/acm/contest/884/C

这个题和南昌网络赛的一个题很相似

 
https://nanti.jisuanke.com/t/38228

两个题一个是一个数列,一个是两个数列,解法都差不多

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int INF = 0x3f3f3f3f;
const int Maxn = 3e6 + 10;
int L[Maxn] , R[Maxn] ;
ll a[Maxn] , sum[Maxn] ;
ll b[Maxn];
ll minn[Maxn * 4] , maxn[Maxn*4];
int n;
//建树
void build(int l ,int r,int root){
    if(l == r){
        minn[root] = maxn[root] = sum[l];
        return;
    }
    int mid =(l + r)>>1;
    build(l , mid , root<<1);
    build(mid + 1 , r ,root<<1|1);
    maxn[root] = max(maxn[root<<1] ,maxn[root<<1|1]);
    minn[root] = min(minn[root<<1] ,minn[root<<1|1]);
}
//求最大值
ll qmax(int l , int r , int root ,int ql ,int qr){
    if(l >= ql && r<= qr){
        return maxn[root];
    }
    int mid = l+ r >>1;
    ll ans = -1e8;
    if(mid >= ql)
        ans = qmax(l ,mid , root * 2 ,ql ,qr);
    if(mid < qr)
        ans = max(ans ,qmax(mid + 1 ,r,root * 2 + 1,ql , qr));
    return ans;
}
//求最小值
ll qmin(int l ,int r , int root ,int ql ,int qr){
    if(l >= ql && r <= qr) return minn[root];
    int mid = (l + r )>> 1;
    ll ans = 1e18;
    if(mid >= ql)
        ans = qmin(l ,mid , root * 2,ql,qr);
    if(mid < qr)
        ans = min(ans ,qmin(mid + 1,r ,root * 2 + 1 , ql,qr));
    return ans;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
 
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        sum[i] = sum[i-1] + b[i];
        L[i] = i;R[i] = i;
    }
    build(1 , n , 1);
    a[0] = a[n + 1] = -INF;//跳出循环
//找每个点的左区间
    for(int i = 1;i <= n;i++){
        while(a[i] <= a[L[i] - 1]){
            L[i] = L[L[i] - 1];  //优化
        }
    }
//反向遍历求出每个点的右区间
    for(int i = n;i >= 1;i--){
        while(a[i] <= a[R[i] + 1]){
            R[i] =R[R[i]+1]; //优化
        }
    }
 
    ll ans = -1e18;
    for(int i = 1;i <= n;i++){
        if(a[i] > 0){ //对于每一点 如果为正数,直接求
            ans = max(ans , a[i] * (sum[R[i]] - sum[L[i] - 1]));
        }else{//如果为负数的话,用右区间的最小前缀和减去左区间的最大前缀和
            ans = max(ans , a[i]*(qmin(1 , n , 1 , i, R[i]) - max(0ll,qmax(1 , n , 1 , L[i] , i))));
        }
    }
    printf("%lld\n",ans);
    //system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注