单调栈求每个数在哪些区间是最值的经典操作。
把数一个一个丢进单调栈，弹出的时候[st[top-1]+1,i-1]这段区间就是弹出的数为最值的区间。
poj2796 弹出的时候更新答案即可
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=500010,inf=1e9; int n,top,ansl,ansr; ll ans=-1; int st[maxn],a[maxn]; ll sum[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int main() { read(n); for(int i=1;i<=n;i++)read(a[i]),sum[i]=sum[i-1]+a[i];a[++n]=-1; for(int i=1;i<=n;i++) { for(;top&&a[i]<=a[st[top]];top--) { ll val=1ll*a[st[top]]*(sum[i-1]-sum[st[top-1]]); if(val>ans)ans=val,ansl=st[top-1]+1,ansr=i-1; } st[++top]=i; } printf("%lld %d %d",ans,ansl,ansr); return 0; }
51nod1215 求出最大值对答案的贡献之和与最小值对答案的贡献之和相减即可。
显然贡献为a[i]*(i-st[top])*(st1[top]-st[top-1]);
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=500010,inf=1e9; int n,top1,top2; int a[maxn],b[maxn],st1[maxn],st2[maxn]; ll mx,mn; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int main() { read(n); for(int i=1;i<=n;i++)read(a[i]),b[i]=a[i];b[++n]=inf; for(int i=1;i<=n;i++) { for(;top1&&a[i]<=a[st1[top1]];top1--) mn+=1ll*a[st1[top1]]*(i-st1[top1])*(st1[top1]-st1[top1-1]); for(;top2&&b[i]>=b[st2[top2]];top2--) mx+=1ll*b[st2[top2]]*(i-st2[top2])*(st2[top2]-st2[top2-1]); st1[++top1]=st2[++top2]=i; } printf("%lld ",mx-mn); return 0; }