【水】关于线段树

回复帖子

@wmsh 2021-05-04 21:37 回复

我就想问下我的线段树是不是写挂了


刚刚蒟蒻做P2894

#include <bits/stdc++.h>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll; 
const int MAXN=60005;
ll n,m;
struct tt{
    ll ma;
    ll lm,rm;
    ll len;
    ll la;
}t[MAXN<<2];
void buildtree(ll l,ll r,ll k){
    t[k].la=0;
    t[k].ma=r-l+1;
    t[k].len=r-l+1;
    t[k].lm=r-l+1;
    t[k].rm=r-l+1;
    if(l==r)return;
    buildtree(l,mid,ls);
    buildtree(mid+1,r,rs);
}
void pushdown(ll k){
    if(t[k].la==0)return;
    if(t[k].la==1){
        t[ls].la=t[rs].la=1;
        t[ls].lm=t[ls].ma=t[ls].rm=0;
        t[rs].lm=t[rs].ma=t[rs].rm=0;
    }
    else if(t[k].la==2){
        t[ls].la=t[rs].la=2;
        t[ls].lm=t[ls].ma=t[ls].rm=t[ls].len;
        t[rs].lm=t[rs].ma=t[rs].rm=t[rs].len;
    }
    t[k].la=0;
}
void pushup(ll k){
    if(t[ls].ma==t[ls].len){
        t[k].lm=t[ls].len+t[rs].lm;
    }
    else t[k].lm=t[ls].lm;
    if(t[rs].ma==t[rs].len){
        t[k].rm=t[ls].rm+t[rs].len;
    }
    else t[k].rm=t[rs].rm;
    t[k].ma=max(t[ls].ma,max(t[rs].ma,t[ls].rm+t[rs].lm));
}
ll query(ll l,ll r,ll k,ll x){
    pushdown(k);
    if(l==r)return l;
    if(t[ls].ma>=x)return query(l,mid,ls,x);
    else if(t[ls].rm+t[rs].lm>=x)return mid-t[ls].rm+1;
    else return query(mid+1,r,rs,x);
    return 0;
}
void update(ll l,ll r,ll k,ll d,ll x,ll y){
    pushdown(k);
    if(x<=l&&r<=y){
        t[k].la=d;
        if(d==1){
            t[k].lm=t[k].ma=t[k].rm=0;
        }
        else t[k].lm=t[k].ma=t[k].rm=t[k].len;
        return;
    }
    if(x<=mid)update(l,mid,ls,d,x,y);
    if(y>mid)update(mid+1,r,rs,d,x,y);
    pushup(k);
}
int main(){
    scanf("%lld%lld",&n,&m);
    buildtree(1,n,1);
    while(m--){
        ll op,x,y;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld",&x);
            if(t[1].ma>=x){
                ll ans=query(1,n,1,x);
                printf("%lld\n",ans);
                update(1,n,1,1,ans,ans+x-1);
            }
            else printf("0\n");
        }
        else{
            scanf("%lld%lld",&x,&y);
            update(1,n,1,2,x,x+y-1);
        }
    }
    return 0;
}

这个75分

#include <bits/stdc++.h>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll; 
const int MAXN=100005;
ll n,m;
struct tt{
    ll ma;
    ll lm,rm;
    ll len;
    ll la;
}t[MAXN<<2];
void buildtree(ll l,ll r,ll k){
    t[k].la=0;
    t[k].ma=r-l+1;
    t[k].len=r-l+1;
    t[k].lm=r-l+1;
    t[k].rm=r-l+1;
    if(l==r)return;
    buildtree(l,mid,ls);
    buildtree(mid+1,r,rs);
}
void pushdown(ll k){
    if(t[k].la==0)return;
    if(t[k].la==1){
        t[ls].la=t[rs].la=1;
        t[ls].lm=t[ls].ma=t[ls].rm=0;
        t[rs].lm=t[rs].ma=t[rs].rm=0;
    }
    if(t[k].la==2){
        t[ls].la=t[rs].la=2;
        t[ls].lm=t[ls].ma=t[ls].rm=t[ls].len;
        t[rs].lm=t[rs].ma=t[rs].rm=t[rs].len;
    }
    t[k].la=0;
}
void pushup(ll k){
    if(t[ls].ma==t[ls].len){
        t[k].lm=t[ls].len+t[rs].lm;
    }
    else t[k].lm=t[ls].lm;
    if(t[rs].ma==t[rs].len){
        t[k].rm=t[ls].rm+t[rs].len;
    }
    else t[k].rm=t[rs].rm;
    t[k].ma=max(t[ls].ma,max(t[rs].ma,t[ls].rm+t[rs].lm));
}
ll query(ll l,ll r,ll k,ll x){
    pushdown(k);
    if(l==r)return l;
    if(t[ls].ma>=x)return query(l,mid,ls,x);
    else if(t[ls].rm+t[rs].lm>=x)return mid-t[ls].rm+1;
    else return query(mid+1,r,rs,x);
    return 0;
}
void update(ll l,ll r,ll k,ll d,ll x,ll y){
    pushdown(k);
    if(x<=l&&r<=y){
        t[k].la=d;
        if(d==1){
            t[k].lm=t[k].ma=t[k].rm=0;
        }
        else t[k].lm=t[k].ma=t[k].rm=t[k].len;
        return;
    }
    if(x<=mid)update(l,mid,ls,d,x,y);
    if(y>mid)update(mid+1,r,rs,d,x,y);
    pushup(k);
}
int main(){
    scanf("%lld%lld",&n,&m);
    buildtree(1,n,1);
    while(m--){
        ll op,x,y;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld",&x);
            if(t[1].ma>=x){
                ll ans=query(1,n,1,x);
                printf("%lld\n",ans);
                update(1,n,1,1,ans,ans+x-1);
            }
            else printf("0\n");
        }
        else{
            scanf("%lld%lld",&x,&y);
            update(1,n,1,2,x,x+y-1);
        }
    }
    return 0;
}

这个 AC ,但就改了一个 $ MAXN $ ,为哈啊,是不是线段树挂了

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。