萌新线段树20pts求助

FIRESTARS @ 2024-08-19 21:39:38

#include<bits/stdc++.h>
using namespace std;
int a[1000005],t[4000005],vis[4000005],b[4000005],b2[4000005];
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        t[v]=a[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    t[v]=max(t[v*2],t[v*2+1]);
}
int getmax(int v,int tl,int tr,int l,int r)
{
    if(tl>=l&&tr<=r)return t[v];
    int tm=(tl+tr)/2;
    if(b[v]!=0)
    {
        t[v*2]=t[v];
        t[v*2+1]=t[v];
        b[v*2]=t[v];
        b[v*2+1]=t[v];
        vis[v]=b[v]=0;
    }
    else if(b2[v]!=0)
    {
        t[v*2]+=b2[v]*(tm-tl+1);
        t[v*2+1]+=b2[v]*(tr-tm);
        b2[v*2]+=b2[v];
        b2[v*2+1]+=b2[v];
        b2[v]=0;
    }
    int s1=0,s2=0;
    if(tm>=l)s1=getmax(v*2,tl,tm,l,r);
    if(tm<r)s2=getmax(v*2+1,tm+1,tr,l,r);
    return max(s1,s2);
}
void updata(int v,int tl,int tr,int l,int r,int x)
{
    if(l<=tl&&tr<=r)
    {
        t[v]=x;
        vis[v]=1;b[v]=x;
        return;
    }
    int tm=(tl+tr)/2;
    if(vis[v]!=0)
    {
        t[v*2]=b[v];
        t[v*2+1]=b[v];
        b[v*2]=b[v];
        b[v*2+1]=b[v];
        vis[v]=b[v]=0;
    }
    if(b2[v]!=0)
    {
        t[v*2]=t[v*2]+b2[v*2];
        t[v*2+1]=t[v*2+1]+b2[v*2+1];
        b2[v*2]+=b2[v];
        b2[v*2+1]+=b2[v];
        b2[v]=0;
    }
    if(tm>=l)updata(v*2,tl,tm,l,r,x);
    if(tm<r)updata(v*2+1,tm+1,tr,l,r,x);
    t[v]=max(t[v*2],t[v*2+1]);
    return;
}
void updata2(int v,int tl,int tr,int l,int r,int x)
{
    if(vis[v]!=0)
    {
        t[v*2]=b[v];
        t[v*2+1]=b[v];
        b[v*2]=b[v];
        b[v*2+1]=b[v];
        vis[v]=b[v]=0;
    }
    if(l<=tl&&tr<=r)
    {
        t[v]+=x;b2[v]+=x;
        return;
    }
    int tm=(tl+tr)/2;
    if(b2[v]!=0)
    {
        t[v*2]=t[v*2]+b2[v*2];
        t[v*2+1]=t[v*2+1]+b2[v*2+1];
        b2[v*2]+=b2[v];
        b2[v*2+1]+=b2[v];
        b2[v]=0;
    }
    if(tm>=l)updata2(v*2,tl,tm,l,r,x);
    if(tm<r)updata2(v*2+1,tm+1,tr,l,r,x);
    t[v]=max(t[v*2],t[v*2+1]);
    return;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        int opt,l,r,x;
        cin>>opt;
        if(opt==1)
        {
            cin>>l>>r>>x;
            updata(1,1,n,l,r,x);
        }
        else if(opt==2)
        {
            cin>>l>>r>>x;
            a[l]=r;
            updata2(1,1,n,l,r,x);
        }
        else if(opt==3)
        {
            cin>>l>>r;
            cout<<getmax(1,1,n,l,r)<<'\n';
        }
    }
}

by zhizhenhuyuzhe @ 2024-08-20 07:12:23

dalao……我想……

by _joker_r @ 2024-08-20 07:29:45

@FIRESTARS 你做覆盖操作时要把加法懒标记清空

by FIRESTARS @ 2024-08-20 07:32:01

@_joker_r 我刚刚检查出来了，感谢

现在50分错后一半的点

我看过你帖子了（

by _joker_r @ 2024-08-20 07:36:51

@FIRESTARS 50的话，建议把b数组赋初值，最好别赋0，可以赋一个<-10^9 或 >10^9的数，s1和s2也要赋一个< -10^9的数

by FIRESTARS @ 2024-08-20 07:38:02

@_joker_r 没有，s1和s2没有问题

by _joker_r @ 2024-08-20 07:39:59

@FIRESTARS 不清楚，反正我当时就是因为那几个没赋太小50ptsWA后5个点的

by _joker_r @ 2024-08-20 07:41:19

当时我把0x3f3f3f3f改成0x3f3f3f3f3f3f3f3f就过了

by __crz_qaq__ @ 2024-08-20 08:30:30

@FIRESTARS %%%竟然会线段树

by chenxi2009 @ 2024-08-20 09:11:51

写树链剖分200行疑似UB的我
出来调线段树
然后自己写了一遍

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[1000001],op,x,y,z,mx[4000001],asn[4000001],add[4000001];
const int X = 1e18;
inline void pushup(int k){
    mx[k] = max(mx[k << 1],mx[k << 1 | 1]);
    return;
}
void build(int k,int l,int r){
    if(l == r){
        mx[k] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(k << 1,l,mid);
    build(k << 1 | 1,mid + 1,r);
    pushup(k);
    return;
}
inline void pushdown(int k){
    if(asn[k] != X){
        asn[k << 1] = asn[k << 1 | 1] = mx[k << 1] = mx[k << 1 | 1] = asn[k];
        add[k << 1] = add[k << 1 | 1] = 0;
    }
    else{
        mx[k << 1] = mx[k << 1] + add[k];
        mx[k << 1 | 1] = mx[k << 1 | 1] + add[k];
        add[k << 1] = add[k << 1] + add[k];
        add[k << 1 | 1] = add[k << 1 | 1] + add[k];
    }
    asn[k] = X,add[k] = 0;
    return;
}
void cge(int k,int l,int r,int x,int y,int num){
    if(y < l || x > r){
        return;
    }
    if(x <= l && y >= r){
        mx[k] = asn[k] = num;
        add[k] = 0;
        return;
    }
    if(asn[k] != X || add[k]){
        pushdown(k);
    }
    int mid = l + r >> 1; 
    cge(k << 1,l,mid,x,y,num);
    cge(k << 1 | 1,mid + 1,r,x,y,num);
    pushup(k);
    return;
}
void upd(int k,int l,int r,int x,int y,int num){
    if(y < l || x > r){
        return;
    }
    if(x <= l && y >= r){
        if(asn[k] != X){
            asn[k] += num;
        }
        else{
            add[k] += num;
        }
        mx[k] += num;
        return;
    }
    if(asn[k] != X || add[k]){
        pushdown(k);
    }
    int mid = l + r >> 1; 
    upd(k << 1,l,mid,x,y,num);
    upd(k << 1 | 1,mid + 1,r,x,y,num);
    pushup(k);
    return;
}
int ask(int k,int l,int r,int x,int y){
    if(y < l || x > r){
        return -1e18;
    }
    if(x <= l && y >= r){
        return mx[k];
    }
    if(asn[k] != X || add[k]){
        pushdown(k);
    }
    int mid = l + r >> 1; 
    return max(ask(k << 1,l,mid,x,y),ask(k << 1 | 1,mid + 1,r,x,y));
}
signed main(){
    for(int i = 0;i <= 4000000;i ++){
        asn[i] = X;
    }
    scanf("%lld%lld",&n,&q);
    for(int i = 1;i <= n;i ++){
        scanf("%lld",&a[i]);
    } 
    build(1,1,n);
    for(int i = 1;i <= q;i ++){
        scanf("%lld",&op);
        if(op == 1){
            scanf("%lld%lld%lld",&x,&y,&z);
            if(y < x){
                swap(x,y);
            }
            cge(1,1,n,x,y,z);
        }
        else if(op == 2){
            scanf("%lld%lld%lld",&x,&y,&z);
            if(y < x){
                swap(x,y);
            }
            upd(1,1,n,x,y,z);
        }
        else{
            scanf("%lld%lld",&x,&y);
            if(y < x){
                swap(x,y);
            }
            printf("%lld\n",ask(1,1,n,x,y));
        }
    }
    return 0;
}

喜提WA60分？？？ @FIRESTARS

by FIRESTARS @ 2024-08-20 09:13:40

@chenxi2009 QwQ大佬我自己都没调出来

验证码8tmd