本文主要是介绍(Nowcoder) C.sequence (线段树+单调队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
和南昌邀请赛的网路赛一模一样。
线段树维护l~r的前缀和即可，但是要注意sum[0]的存在，建树时并没有将其考虑进去。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=LONG_LONG_MAX;
const double pi=acos(-1.0);
const double eps=1e-9;
const int maxn=3e6+5;
//il int Add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll x,int y) {return x*y>=mod?x*y%mod:x*y;}
ll sum[maxn];
int a[maxn],b[maxn],n;
struct node{ll mx,mi;
}s[maxn<<2];
il void pushup(int rt){s[rt].mx=max(s[rt<<1].mx,s[rt<<1|1].mx);s[rt].mi=min(s[rt<<1].mi,s[rt<<1|1].mi);
}
il void build(int l,int r,int rt){if(l==r){s[rt].mx=s[rt].mi=sum[l];return ;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);
}
il ll qmx(int L,int R,int l,int r,int rt){if(L>r || R<l) return -inf;if(L<=l && R>=r) return s[rt].mx;int mid=(l+r)>>1;return max(qmx(L,R,l,mid,rt<<1),qmx(L,R,mid+1,r,rt<<1|1));
}
il ll qmi(int L,int R,int l,int r,int rt){if(L>r || R<l) return inf;if(L<=l && R>=r) return s[rt].mi;int mid=(l+r)>>1;return min(qmi(L,R,l,mid,rt<<1),qmi(L,R,mid+1,r,rt<<1|1));
}
int st[maxn],L[maxn],R[maxn];
int main(){std::ios::sync_with_stdio(0);cin>>n;int top=0,tl=0;rep(i,1,n){cin>>a[i];while(top>0 && a[i]<=a[st[top]]){R[st[top]]=i-1;top--; }if(top==0) L[i]=1;else L[i]=st[top]+1;st[++top]=i;} while(top){R[st[top]]=n;top--;}rep(i,1,n){cin>>b[i];sum[i]=sum[i-1]+b[i];}build(1,n,1);ll ans=-inf;rep(i,1,n){if(a[i]>0){ll rmx=qmx(i,R[i],1,n,1);ll lmi=qmi(L[i]-1,i-1,1,n,1);if(lmi>0 && L[i]-1==0) lmi=0;ans=max(ans,(rmx-lmi)*(ll)a[i]);}else{ll rmi=qmi(i,R[i],1,n,1);ll lmx=qmx(L[i]-1,i-1,1,n,1);if(lmx<0 && L[i]-1==0) lmx=0;ans=max(ans,(rmi-lmx)*(ll)a[i]);}}cout<<ans<<endl;return 0;
}
这篇关于(Nowcoder) C.sequence (线段树+单调队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
