首页 > 其他 > 详细

array「单调栈」

时间:2019-10-12 22:13:08      阅读:100      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

范围$1e7$,$a<=1e9$

让求得就是对于每个$i$,找到比$i$靠左,而$a[j]$比$a[i]$大的第一个位置,找到最小值下标

然后最简单维护方法是线段树

60分代码

技术分享图片
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 11111111
ll a[A],lsh[A],tong[A];
ll ida,minn,maxpla,nowval;
struct tree{
    ll l,r,id,val,mx;
}tr[A];
struct node{
    ll val,id;
    node(){}
    node(const ll &a,const ll &b){val=a,id=b;}
    friend bool operator < (const node &a,const node &b){
        return a.val<b.val;
    }
}now,pre;
ll n,id,ans;
set<node>st;
set<node>::iterator it;
void built(ll x,ll l,ll r){
    tr[x].l=l,tr[x].r=r;
    if(l==r){
        scanf("%lld",&a[l]);
        tr[x].val=a[l];
        tr[x].id=l;
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
    if(tr[x<<1].val<=tr[x<<1|1].val){
        tr[x].val=tr[x<<1].val;
        tr[x].id=tr[x<<1].id;
    }
    else {
        tr[x].val=tr[x<<1|1].val;
        tr[x].id=tr[x<<1|1].id;
    }
}
void seg_min(ll x,ll l,ll r){
    if(tr[x].l>=l&&tr[x].r<=r){
        if(tr[x].val==minn){
            ida=min(ida,tr[x].id);
        }
        else if(tr[x].val<minn){
            minn=tr[x].val;
            ida=tr[x].id;
        }
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=l) seg_min(x<<1,l,r);
    if(mid<r) seg_min(x<<1|1,l,r);
}
void find(ll x){
    if(tr[x].mx<=nowval) return ;
    if(tr[x].l==tr[x].r){
        maxpla=max(tr[x].l,maxpla);
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(tr[x<<1|1].mx>nowval) find(x<<1|1);
    else if(tr[x<<1].mx>nowval)find(x<<1);
}
void chose(ll x,ll ql,ll qr){
    if(tr[x].l>=ql&&tr[x].r<=qr){
        find(x);
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=ql) chose(x<<1,ql,qr);
    if(mid<qr) chose(x<<1|1,ql,qr);
}
void change(ll x,ll pla,ll val){
    if(tr[x].l==tr[x].r){
        tr[x].mx=val;
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=pla) change(x<<1,pla,val);
    else change(x<<1|1,pla,val);
    tr[x].mx=max(tr[x<<1].mx,tr[x<<1|1].mx);
}
int main(){
    scanf("%lld",&n);
    built(1,1,n);
    for(ll i=1;i<=n;i++){
        ida=0,minn=0x7ffffffffffff;
        maxpla=0,nowval=a[i];
        chose(1,1,i-1);
        change(1,i,a[i]);
        seg_min(1,maxpla+1,i);
//        printf("maxpla=%lld nowval=%lld minn=%lld i-ida+1=%lld\n",maxpla,nowval,minn,i-ida+1);
        ans=max(i-ida+1,ans);
    }
    printf("%lld\n",ans);
}
View Code

技术分享图片

 

array「单调栈」

原文:https://www.cnblogs.com/znsbc-13/p/11663986.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!