题目背景
GD是一个热衷于寻求美好事物的人，一天他拿到了一个美丽的序列。
题目描述
为了研究这个序列的美丽程度，GD定义了一个序列的“美丽度”和“美丽系数”：对于这个序列的任意一个区间[l，r]，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积，而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。现在GD想要你帮忙计算这个序列的“美丽系数”。
输入输出格式
输入格式：
第一行一个整数n，代表序列中的元素个数。 第二行n个整数a1、a2„an，描述这个序列。
输出格式：
一行一个整数，代表这个序列的“美丽系数”。
输入输出样例
输入样例#1：
3
1 2 3
输出样例#1：
4
说明
样例解释 选取区间［2，3］，可以获得最大“美丽系数”为2*2=4。 数据范围 对于20%的数据，n<=2000； 对于60%的数据，n<=200000； 对于100%的数据，1<=n<=2000000，0<=ai<=2000000。 提示 你可能需要一个读入优化。
用线段树+维护区间最小值，构造一颗笛卡尔树+卡时可以过
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define LL long long
inline int read() {
int x=;
char c=getchar();
while(c<''||c>'')c=getchar();
while(c<=''&&c>='')x=x*+c-'',c=getchar();return x;
}
const int INF = 0x7fffffff;
const int maxn = ;
int a[maxn];
int n;LL ans=;
struct node{
int w,pos;
}tree[maxn<<];
inline void update(int rt) {
tree[rt].pos=tree[rt<<].w < tree[rt<<|].w ? tree[rt<<].pos :tree[rt<<|].pos;
tree[rt].w=min(tree[rt<<].w,tree[rt<<|].w);
}
void build(int l,int r,int rt) {
if(l==r) {
tree[rt].w=a[l]=read();tree[rt].pos=l;return;
}
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
update(rt);
}
int query(int l,int r,int rt,int tl,int tr) {
if(tl<=l&&tr>=r) return tree[rt].pos;
int a1,m=0x7fffffff;
int mid=(l+r)>>;
if(tl<=mid){
int tmp=query(l,mid,rt<<,tl,tr);
if(m>a[tmp])m=a[tmp],a1=tmp;
}
if(tr>mid) {
int tmp=query(mid+,r,rt<<|,tl,tr);
if(m>a[tmp])m=tree[tmp].w,a1=tmp;
}
return a1;
}
int cnt=;
void dfs(int p,int l,int r) {
++cnt;
if(cnt==) {
printf("%lld\n",ans);exit();
}
if(l==r) {
ans=a[l]>ans?a[l]:ans;return;
}
ans=ans<(LL)(r-l+)*a[p]?(LL)(r-l+)*a[p]:ans;
if(p>l)dfs(query(,n,,l,p-),l,p-);
if(p<r)dfs(query(,n,,p+,r),p+,r);
}
int main() {
n=read();int minn=INF,pos;
build(,n,);
dfs(tree[].pos,,n);
printf("%lld\n",ans);
return ;
}
线段树
维护两个单调队列，求出当每个点为最小值是向左右扩展的最大距离
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn= ;
#ifdef WIN32
#define lld "I64d"
#else
#define lld "lld"
#endif
inline int read() {
int x=;
char c=getchar();
while(c<''||c>'')c=getchar();
while(c<=''&&c>='')x=x*+c-'',c=getchar();return x;
}
int a[maxn],b[maxn];
int l[maxn],r[maxn],tmp[maxn],q[maxn];
int n,m;
void work(int c[] ,int d[]) {
q[]=c[]; tmp[]=;
int head=,tail=;
for(int i=;i<=n;++i) {
while(head<=tail&&q[tail]>c[i]) d[tmp[tail--]]=i-;
q[++tail]=c[i];
tmp[tail]=i;
}
while(head<=tail) d[tmp[head++]]=n;
}
int main() {
LL ans=;
n=read();
for(int i=;i<=n;++i)
a[i]=read(),b[n-i+]=a[i];
work(a,r);
work(b,l);
for(int i=;i<=n;++i) tmp[i]=l[i];
for(int i=;i<=n;++i) l[n-i+]=n-tmp[i]+;
for(int i=;i<=n;++i) ans=max(ans,1ll*a[i]*(r[i]-l[i]+));
printf("%lld\n",ans);
return ;
}
单调队列