洛谷——P2659 美丽的序列

洛谷——P2659 美丽的序列

P2659 美丽的序列

 

单调栈维护区间最小值，单调递增栈维护区间最小值，

考虑当前数对答案的贡献，不断加入数，如果加入的数$>$栈顶，说明栈顶的元素对当前数所在区间是有贡献的，同时加入当前的数。

反之，若当前加入的数比栈顶元素小，那么栈顶元素（所谓的最小值）已经失去了价值，因为他不会再对后面的区间造成影响，所以弹出栈顶，同时更新$ans$

 

#include<iostream>
#include<cstdio>
#include<algorithm>#define N 10000000
#define inf 0x7fffffff
#define LL long long
using namespace std;LL ans,top;
struct node{int val,pos;
}S[N];
int n;int main()
{scanf("%d",&n);for(int x,i=1;i<=n;i++){scanf("%d",&x);if(!top) S[++top].val=x,S[top].pos=i;else{while(S[top].val>x) {ans=max(ans,1ll*(i-S[top-1].pos-1)*S[top].val);--top;}S[++top].pos=i,S[top].val=x;}}for(int i=1;i<=top;i++)ans=max(ans,1ll*(n-S[i-1].pos)*S[i].val);printf("%lld",ans);return 0;
}

 

线段树查询区间最小值，找到区间最小值的位置，不断递归寻找最小值。

一段区间的价值即为$(r-l+1)*minn$

这种做法竟然没有$TLE$，神奇，难道就是因为他不断递归找了最小值的位置吗？

 

#include<iostream>
#include<cstdio>
#include<algorithm>#define N 10000000
#define inf 0x7fffffff
using namespace std;struct nodE{int l,r,w_max,pos;
}tr[N];int n;
long long ans;void push_up(int k){if(tr[k<<1].w_max<tr[k<<1|1].w_max) tr[k].pos=tr[k<<1].pos;else tr[k].pos=tr[k<<1|1].pos;tr[k].w_max=min(tr[k<<1].w_max,tr[k<<1|1].w_max);
}void build(int k,int l,int r){tr[k].l=l,tr[k].r=r;if(l==r) {scanf("%d",&tr[k].w_max);tr[k].pos=l;return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);push_up(k);
}nodE query(int k,int ql,int qr){int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;if(l>=ql&&r<=qr) return tr[k];nodE x,y;x.w_max=y.w_max=inf;if(ql<=mid) x=query(k<<1,ql,qr);if(qr>mid) y=query(k<<1|1,ql,qr);return x.w_max>y.w_max ? y :x;
}void slove(int l,int r){nodE px=query(1,l,r);ans=max(ans,1ll*(r-l+1)*px.w_max);if(l<px.pos) slove(l,px.pos-1);if(r>px.pos) slove(px.pos+1,r);
}int main()
{scanf("%d",&n);build(1,1,n);slove(1,n);printf("%lld",ans);return 0;
}

 

转载于:.html