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=;

    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 ;

}

单调队列

巴特西

luogu P2659 美丽的序列

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章