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=;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-].pos-)*S[top].val);--top;}

            S[++top].pos=i,S[top].val=x;

        }

    }

    for(int i=;i<=top;i++)

        ans=max(ans,1ll*(n-S[i-].pos)*S[i].val);

    printf("%lld",ans);

    return ;

}

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

一段区间的价值即为$(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<<].w_max<tr[k<<|].w_max) tr[k].pos=tr[k<<].pos;

    else tr[k].pos=tr[k<<|].pos;

    tr[k].w_max=min(tr[k<<].w_max,tr[k<<|].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)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    push_up(k);

}

nodE query(int k,int ql,int qr){

    int l=tr[k].l,r=tr[k].r,mid=(l+r)>>;

    if(l>=ql&&r<=qr) return tr[k];

    nodE x,y;x.w_max=y.w_max=inf;

    if(ql<=mid) x=query(k<<,ql,qr);

    if(qr>mid) y=query(k<<|,ql,qr);

    return x.w_max>y.w_max ? y :x;

}

void slove(int l,int r){

    nodE px=query(,l,r);

    ans=max(ans,1ll*(r-l+)*px.w_max);

    if(l<px.pos) slove(l,px.pos-);

    if(r>px.pos) slove(px.pos+,r);

}

int main()

{

    scanf("%d",&n);

    build(,,n);

    slove(,n);

    printf("%lld",ans);

    return ;

}

巴特西

洛谷——P2659 美丽的序列

P2659 美丽的序列

最新文章

热门文章