2019南昌邀请赛网络赛 I.Max answer

亦凉 2021-09-19 00:54 330阅读 0赞

单调栈维护左边和右边第一个大于它的位置  
用ST表维护区间前缀和的最大值和最小值  
当前点小于0的时候就是 后 半 部 分 S m i n − 前 半 部 分 S m a x 后半部分Smin-前半部分Smax 后半部分Smin−前半部分Smax  
大于0的时候就是 后 半 部 分 S m a x − 前 半 部 分 S m i n 后半部分Smax-前半部分Smin 后半部分Smax−前半部分Smin

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 5e5+1000;
    
    ll stm[maxn][23];
    ll stn[maxn][23];
    
    int n;
    int a[maxn];
    ll s[maxn];
    int l[maxn],r[maxn];
    
    
    ll Querym(int l,int r)
    { 
        int k=log2(r-l+1); 
        return max(stm[l][k],stm[r-(1<<k)+1][k]);
    }
    
    ll Queryn(int l,int r)
    { 
        int k=log2(r-l+1); 
        return min(stn[l][k],stn[r-(1<<k)+1][k]);
    }
    
    
    int main()
    { 
        cin >> n;
        rep(i,1,n+1) cin >> a[i];
        rep(i,1,n+1) s[i] = s[i-1] + a[i];
        rep(i,0,n+1) stm[i][0] = stn[i][0] = s[i];
        for(int j=1;j<=21;j++)
            for(int i=0;i+(1<<j)-1<=n;i++)
                { 
                	stm[i][j]=max(stm[i][j-1],stm[i+(1<<(j-1))][j-1]);
                	stn[i][j]=min(stn[i][j-1],stn[i+(1<<(j-1))][j-1]);
                }
        stack<int> sta;
    
       	rep(i,1,n+1)
        { 
            while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
            if (sta.empty()) l[i]=1; else l[i]=sta.top()+1;
            sta.push(i);
        }
        while (!sta.empty()) sta.pop();
       	per(i,1,n+1)
        { 
            while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
            if (sta.empty()) r[i]=n; else r[i]=sta.top()-1;
            sta.push(i);
        }
        ll ans = -1e16;
        rep(i,1,n+1)
        { 
        	if(a[i] > 0)
        	{ 
        		ll rrr = Querym(i,r[i]);
        		ll lll = Queryn(l[i]-1,i-1);
        		ans = max(ans,(rrr-lll)*(ll)a[i]);
        	}
        	else if(a[i] < 0)
        	{ 
        		ll rrr = Queryn(i,r[i]);
        		ll lll = Querym(l[i]-1,i-1);
        		ans = max(ans,(rrr-lll)*(ll)a[i]);	
        	}
        	else
        	{ 
        		ans = max(0ll,ans);
        	}
        }
        cout << ans << endl;
    }