array「单调栈」 | Hexo

归档于 2019-10-12 21:18

范围$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