大佬求调

ZY_jiang @ 2024-04-19 19:26:52

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
#define ls u<<1
#define rs u<<1|1
#define mid (tr[u].l+tr[u].r)>>1
#define mdi (l+r)>>1
using namespace std;
const int N=1e5+10;
struct tree{
    ll l,r,pos,lazy,maxn,change;
} tr[N*4];
ll n,m,a[N];
//void pushup(ll u){
//  tr[u].pos=tr[ls].pos+tr[rs].pos;
//  return ;
//}
void maxnup(ll u){
//  tr[u].maxn=(tr[ls].pos,tr[rs].pos);
    tr[u].maxn=max(tr[ls].maxn,tr[rs].maxn);
//  cout<<u<<" "<<tr[u].maxn<<endl;
    return ;
}
void changedown(ll u){
    if(tr[u].change){
        tr[ls].maxn=tr[u].change;
        tr[rs].maxn=tr[u].change;
        tr[ls].change=tr[u].change;
        tr[rs].change=tr[u].change;
        tr[u].change=0;
    }
}
void pushdown(ll u){
    if(tr[u].lazy){
        tr[ls].maxn+=tr[u].lazy;
        tr[rs].maxn+=tr[u].lazy;
        tr[ls].lazy+=tr[u].lazy;
        tr[rs].lazy+=tr[u].lazy;
        tr[u].lazy=0;
    }
    return ;
}
void build(ll u,ll l,ll r){
    tr[u].l=l;
    tr[u].r=r;
    if(l==r){
        tr[u].maxn=a[l];
        return ;
    }
    ll m=(l+r)>>1;
    build(ls,l,m);
    build(rs,m+1,r);
    maxnup(u);
    return ;
}
// 加x 
void add(ll u,ll l,ll r,ll k){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].maxn+=k;
        tr[u].lazy=k;
        return ;
    }
    pushdown(u);
    if(l<=mid) add(ls,l,r,k);
    if(mid<r) add(rs,l,r,k);
    maxnup(u);
    return ;
}
// 改值 
void change(ll u,ll l,ll r,ll k){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].maxn=k;
        tr[u].change=k;
        return ;
    }
    changedown(u);
    maxnup(u);
    if(l<=mid) change(ls,l,r,k);
    if(mid<r) change(rs,l,r,k);
    return ;
}
// 最大值 
ll memery(ll u,ll l,ll r){
//  maxnup(u);
    if(l<=tr[u].l&&tr[u].r<=r){
        return tr[u].maxn;
    }
    changedown(u);
    pushdown(u);
    ll ans=-INT_MAX;
    if(l<=mid) ans=max(ans,memery(ls,l,r));
    if(r>mid) ans=max(ans,memery(rs,l,r));
    return ans;
}
int main(){
    cin>>n>>m;
    F(i,1,n){
        cin>>a[i];
    }
    build(1,1,n);
    F(i,1,m){
        ll id,x,y,k;
        cin>>id;
        if(id==1){
            cin>>x>>y>>k;
            change(1,x,y,k);
        }
        else if(id==2){
            cin>>x>>y>>k;
            add(1,x,y,k);
        }
        else{
            cin>>x>>y;
            cout<<memery(1,x,y)<<endl;
        }
    }
}

by hjw100516 @ 2024-04-30 21:43:22

• 1. 数组开小了，要开到1e6
• 2. 在changedown中不能判断“ tr[u].change ”不为零，因为有些操作会将区间内的所有数更改成零，建议初始化为负无穷。
• 3. 在changedown中没有将加法的懒标记去掉，因为在更改数字后，前面的加法也就无效了。
• 4. 在add中“ tr[u].lazy=”因改为“ tr[u].lazy+=k ”
• 5. 在add中的“ pushdown ”前加上“ changedown ”判断它的值是否要修改
• 6. 在memery中“ ans ”的初值应赋值为负无穷而不是“ -INT_MAX ”
• 7. 读入非常多不能直接用“ cin ”和“ cout ”否则会超时

AC代码如下

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
#define ls u<<1
#define rs u<<1|1
#define mid (tr[u].l+tr[u].r)>>1
#define mdi (l+r)>>1
using namespace std;
const int N=1e6+10;
struct tree{
    ll l,r,pos,lazy,maxn,change;
} tr[N*4];
ll n,m,a[N];
//void pushup(ll u){
//  tr[u].pos=tr[ls].pos+tr[rs].pos;
//  return ;
//}
void maxnup(ll u){
//  tr[u].maxn=(tr[ls].pos,tr[rs].pos);
    tr[u].maxn=max(tr[ls].maxn,tr[rs].maxn);
//  cout<<u<<" "<<tr[u].maxn<<endl;
    return ;
}
void changedown(ll u){
    if(tr[u].change!=LONG_LONG_MIN){
        tr[ls].maxn=tr[u].change;
        tr[rs].maxn=tr[u].change;
        tr[ls].change=tr[u].change;
        tr[rs].change=tr[u].change;
        tr[u].change=LONG_LONG_MIN;
        tr[ls].lazy=tr[rs].lazy=0;
    }
}
void pushdown(ll u){
    if(tr[u].lazy){
        tr[ls].maxn+=tr[u].lazy;
        tr[rs].maxn+=tr[u].lazy;
        tr[ls].lazy+=tr[u].lazy;
        tr[rs].lazy+=tr[u].lazy;
        tr[u].lazy=0;
    }
    return ;
}
void build(ll u,ll l,ll r){
    tr[u].l=l;
    tr[u].r=r;
    tr[u].change=LONG_LONG_MIN;
    if(l==r){
        tr[u].maxn=a[l];
        return ;
    }
    ll m=(l+r)>>1;
    build(ls,l,m);
    build(rs,m+1,r);
    maxnup(u);
    return ;
}
// 加x 
void add(ll u,ll l,ll r,ll k){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].maxn+=k;
        tr[u].lazy+=k;
        return ;
    }
    changedown(u);
    pushdown(u);
    if(l<=mid) add(ls,l,r,k);
    if(mid<r) add(rs,l,r,k);
    maxnup(u);
    return ;
}
// 改值 
void change(ll u,ll l,ll r,ll k){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].maxn=k;
        tr[u].change=k;
        tr[u].lazy=0;
        return ;
    }
    changedown(u);
    pushdown(u);
    if(l<=mid) change(ls,l,r,k);
    if(mid<r) change(rs,l,r,k);
    maxnup(u);
    return ;
}
// 最大值 
ll memery(ll u,ll l,ll r){
//  maxnup(u);
    if(l<=tr[u].l&&tr[u].r<=r){
        return tr[u].maxn;
    }
    changedown(u);
    pushdown(u);
    ll ans=LONG_LONG_MIN;
    if(l<=mid) ans=max(ans,memery(ls,l,r));
    if(r>mid) ans=max(ans,memery(rs,l,r));
    return ans;
}
int main(){
    cin>>n>>m;
    F(i,1,n){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    F(i,1,m){
        ll id,x,y,k;
        scanf("%lld",&id);
        if(id==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            change(1,x,y,k);
        }
        else if(id==2){
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,x,y,k);
        }
        else{
            scanf("%lld%lld",&x,&y);
            cout<<memery(1,x,y)<<endl;
        }
    }
}

by hjw100516 @ 2024-04-30 21:44:50

@ZY_jiang

帮你改了半个小时，是不是很感动