luogu P2659 美丽的序列

题目背景

GD是一个热衷于寻求美好事物的人，一天他拿到了一个美丽的序列。

题目描述

为了研究这个序列的美丽程度，GD定义了一个序列的“美丽度”和“美丽系数”：对于这个序列的任意一个区间[l，r]，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积，而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。现在GD想要你帮忙计算这个序列的“美丽系数”。

输入输出格式

输入格式：

第一行一个整数n，代表序列中的元素个数。第二行n个整数a1、a2„an，描述这个序列。

输出格式：

一行一个整数，代表这个序列的“美丽系数”。

输入输出样例

输入样例#1：复制

3 
1 2 3

输出样例#1：复制

说明

样例解释选取区间［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=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x;
} 
const int INF = 0x7fffffff;
const int maxn = 2000007;
int a[maxn];
int n;LL ans=0;
struct node{
    int w,pos;
}tree[maxn<<2];
inline void update(int rt) {
    tree[rt].pos=tree[rt<<1].w < tree[rt<<1|1].w ? tree[rt<<1].pos :tree[rt<<1|1].pos;
    tree[rt].w=min(tree[rt<<1].w,tree[rt<<1|1].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)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    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)>>1;
    if(tl<=mid){
        int tmp=query(l,mid,rt<<1,tl,tr);
        if(m>a[tmp])m=a[tmp],a1=tmp;    
    }
    if(tr>mid) {
        int tmp=query(mid+1,r,rt<<1|1,tl,tr);
        if(m>a[tmp])m=tree[tmp].w,a1=tmp;    
    }
    return a1;
}
int cnt=0;
void dfs(int p,int l,int r) {
    ++cnt;
    if(cnt==1200000) {
        printf("%lld
",ans);exit(0);
    }
    if(l==r) {
        ans=a[l]>ans?a[l]:ans;return;
    }
    ans=ans<(LL)(r-l+1)*a[p]?(LL)(r-l+1)*a[p]:ans;
    if(p>l)dfs(query(1,n,1,l,p-1),l,p-1);
    if(p<r)dfs(query(1,n,1,p+1,r),p+1,r);
}
int main() {
    n=read();int minn=INF,pos;
    build(1,n,1);
    dfs(tree[1].pos,1,n);
    printf("%lld
",ans);
    return 0;
}

线段树

维护两个单调队列，求出当每个点为最小值是向左右扩展的最大距离

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long 
const int maxn= 2000007;
#ifdef WIN32
#define lld "I64d"
#else
#define lld "lld"
#endif
inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c<='9'&&c>='0')x=x*10+c-'0',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[1]=c[1]; tmp[1]=1;
    int head=1,tail=1;
    for(int i=2;i<=n;++i) {
        while(head<=tail&&q[tail]>c[i]) d[tmp[tail--]]=i-1;
        q[++tail]=c[i];
        tmp[tail]=i;
       }
       while(head<=tail) d[tmp[head++]]=n;
}
int main() {
    LL ans=0;
    n=read();
    for(int i=1;i<=n;++i) 
        a[i]=read(),b[n-i+1]=a[i];
    work(a,r);
    work(b,l);
    for(int i=1;i<=n;++i) tmp[i]=l[i];
    for(int i=1;i<=n;++i) l[n-i+1]=n-tmp[i]+1;
    for(int i=1;i<=n;++i) ans=max(ans,1ll*a[i]*(r[i]-l[i]+1));
    printf("%lld
",ans);
    return 0;
}

单调队列