牛客

第四场C：Sequence
https://ac.nowcoder.com/acm/contest/884/C
线段树维护区间最值，单调栈维护每个数影响的最大区间
*

#include<bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    struct tree
    {
        ll l,r,minn,maxn;
    } t[3000100*5];
    struct node
    {
        ll num,l,r;
    } a[3000100];
    ll b[3000100];
    
    
    void build(int rt,int l,int r)
    {
        t[rt].l=l;
        t[rt].r=r;
        if(l==r)
        {
            t[rt].minn=b[l],t[rt].maxn=b[l];
            return ;
        }
        int mid=(l+r)/2;
    
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
        t[rt].maxn=max(t[rt*2].maxn,t[rt*2+1].maxn);
        t[rt].minn=min(t[rt*2].minn,t[rt*2+1].minn);
    }
    
    ll querymax(int rt,int x,int y)
    {
        if(x<=t[rt].l&&y>=t[rt].r)
        {
            return t[rt].maxn;
        }
        else
        {
            int mid=(t[rt].l+t[rt].r)/2;
            ll ans1=-1e10,ans2=-1e10;
    
            if(x<=mid)
            {
                ans1 =  querymax(rt*2,x,y);
            }
            if(y>mid)
            {
                ans2 = querymax(rt*2+1,x,y);
            }
            return max(ans1,ans2);
        }
    }
    
    ll querymin(int rt,int x,int y)
    {
        if(x<=t[rt].l&&y>=t[rt].r)
        {
            return t[rt].minn;
        }
        else
        {
            int mid=(t[rt].l+t[rt].r)/2;
            ll ans1=1e10,ans2=1e10;
            if(x<=mid)
            {
                ans1 = querymin(rt*2,x,y);
            }
            if(y>mid)
            {
                ans2 =  querymin(rt*2+1,x,y);
            }
            return min(ans1,ans2);
        }
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=1; i<=n; i++)
                scanf("%lld",&a[i].num);
            for(int i=1; i<=n; i++)
                scanf("%lld",&b[i]),b[i]+=b[i-1];
    
            a[n+1].num=-1e7;
            a[0].num=-1e7;
            stack<int>stk;
            for(int i=1; i<=n+1; i++)
            {
                while(!stk.empty()&&a[stk.top()].num>a[i].num)
                {
                    int top=stk.top();
                    stk.pop();
    
                    a[top].r=i-1;
                }
                stk.push(i);
            }
            while(!stk.empty())
                stk.pop();
            for(int i=n; i>=0; i--)
            {
                while(!stk.empty()&&a[stk.top()].num>a[i].num)
                {
                    int top=stk.top();
                    stk.pop();
    
                    a[top].l=i+1;
                }
                stk.push(i);
            }
            build(1,1,n);
            ll ans=0;
            for(int i=1; i<=n; i++)
            {
                if(a[i].num<0)
                {
                    ll minn=querymin(1,i,a[i].r);
                    ll maxn=querymax(1,a[i].l-1,i-1);
                   // printf("%d-%d\n",minn,maxn);
                    ans=max(ans,(minn-maxn)*a[i].num);
                }
                else if(a[i].num>0)
                {
                    ll minn=querymin(1,a[i].l-1,i-1);
                    ll maxn=querymax(1,i,a[i].r);
                 //   printf("%d+%d\n",minn,maxn);
                  ans=max(ans,(maxn-minn)*a[i].num);
                   // ans=max(ans,(b[a[i].r]-b[a[i].l-1])*a[i].num);
                }
    
            }printf("%lld\n",ans);
    
        }
    }