萌新刚学线段树，20分求调

kk1501201 @ 2023-09-27 15:56:16

#include<bits/stdc++.h>
#include<unistd.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
const int N=3e6+1;
const ll INF=1e11+7;
struct Tree
{
    int lson,rson;
    ll sum,tagadd=0,tagchange=INF;  
}a[N];
ll A[N];
void pushup(int u)
{
    a[u].sum=max(a[a[u].lson].sum,a[a[u].rson].sum);
}
void pushdown(int u,int l,int r)
{
    if(a[u].tagadd==0&&a[u].tagchange==INF)return;
    int mid=l+r>>1;
    if(a[u].tagchange!=INF)
    {
        a[a[u].lson].tagadd=0;
        a[a[u].rson].tagadd=0;
        a[a[u].lson].tagchange=a[u].tagchange;
        a[a[u].rson].tagchange=a[u].tagchange;
        a[a[u].lson].sum=a[u].tagchange;
        a[a[u].rson].sum=a[u].tagchange;
    }
    a[a[u].lson].sum+=a[u].tagadd;
    a[a[u].rson].sum+=a[u].tagadd;
    a[u].tagadd=0; 
    a[u].tagchange=INF; 
} 
int t=1;
int x,y;
void build(int u,int l,int r)
{
    if(l==r)
    {
        a[u].sum=A[l];//单点，值等于它原本的值
        return ; 
    }
    int mid=l+r>>1;
    a[u].lson=++t;//开节点，建线段树 
    build(a[u].lson,l,mid);
    a[u].rson=++t;
    build(a[u].rson,mid+1,r); 
    pushup(u);
}
bool flag;//0改 1加法 
void update(int u,int l,int r,ll w)
{
    if(x<=l&&r<=y)
    {
        if(flag) 
        {
            a[u].tagadd+=w;
            a[u].sum+=w;
        }
        else
        {
            a[u].tagadd=0;
            a[u].tagchange=w; 
            a[u].sum=w;
        }
        return ;
    } 
    int mid=l+r>>1;
    pushdown(u,l,r);
    if(x<=mid)update(a[u].lson,l,mid,w);
    if(y>mid)update(a[u].rson,mid+1,r,w);
    pushup(u); 
} 
ll query(int u,int l,int r)//区间查询（从u号节点在l到r之间查询fl到rl的值) 
{
    ll ans=-INF;
    if(x<=l&&r<=y)
    {
        return a[u].sum;
    }
    pushdown(u,l,r);
    int mid=l+r>>1;
    if(x<=mid)
    {
        ans=max(ans,query(a[u].lson,l,mid));
    }
    if(y>mid)
    {
        ans=max(ans,query(a[u].rson,mid+1,r));
    }
    pushup(u);
    return ans;
} 
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main()
{
    ll n=read(),m=read();
    for(int i=1;i<=n;i++) A[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        ll op=read();
        x=read(),y=read();
        if(op==3)
        {   
            ll ans=query(1,1,n);
            cout<<ans<<endl;
        }
        else
        {
            if(op==1) flag=0;
            if(op==2) flag=1;
            ll w=read();
            update(1,1,n,w);
        }
    }
    return 0;
}

by QCurium @ 2023-09-27 16:39:12

改完了

#include<bits/stdc++.h>
#include<unistd.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define endl '\n'
using namespace std;
const int N=3e6+1;
const ll INF=1e11+7;
struct Tree
{
    int lson,rson;
    ll sum,tagadd=0,tagchange=INF;  
}a[N];
ll A[N];
void pushup(int u)
{
    a[u].sum=max(a[a[u].lson].sum,a[a[u].rson].sum);
}
void pushdown(int u,int l,int r)
{
    if(a[u].tagadd==0&&a[u].tagchange==INF)return;
    int mid=l+r>>1;
    if(a[u].tagchange!=INF)
    {
        a[a[u].lson].tagadd=0;
        a[a[u].rson].tagadd=0;
        a[a[u].lson].tagchange=a[u].tagchange;
        a[a[u].rson].tagchange=a[u].tagchange;
        a[a[u].lson].sum=a[u].tagchange;
        a[a[u].rson].sum=a[u].tagchange;
    }
    if(a[a[u].lson].tagchange!=INF)
        a[a[u].lson].tagchange+=a[u].tagadd;
    else
        a[a[u].lson].tagadd+=a[u].tagadd;
    if(a[a[u].rson].tagchange!=INF)
        a[a[u].rson].tagchange+=a[u].tagadd;
    else
        a[a[u].rson].tagadd+=a[u].tagadd;
    a[a[u].lson].sum+=a[u].tagadd;
    a[a[u].rson].sum+=a[u].tagadd;
    a[u].tagadd=0; 
    a[u].tagchange=INF; 
} 
int t=1;
int x,y;
void build(int u,int l,int r)
{
    if(l==r)
    {
        a[u].sum=A[l];//单点，值等于它原本的值
        return ; 
    }
    int mid=l+r>>1;
    a[u].lson=++t;//开节点，建线段树 
    build(a[u].lson,l,mid);
    a[u].rson=++t;
    build(a[u].rson,mid+1,r); 
    pushup(u);
}
bool flag;//0改 1加法 
void update(int u,int l,int r,ll w)
{
    if(x<=l&&r<=y)
    {
        if(flag) 
        {
            a[u].tagadd+=w;
            a[u].sum+=w;
        }
        else
        {
            a[u].tagadd=0;
            a[u].tagchange=w; 
            a[u].sum=w;
        }
        return ;
    } 
    int mid=l+r>>1;
    pushdown(u,l,r);
    if(x<=mid)update(a[u].lson,l,mid,w);
    if(y>mid)update(a[u].rson,mid+1,r,w);
    pushup(u); 
} 
ll query(int u,int l,int r)//区间查询（从u号节点在l到r之间查询fl到rl的值) 
{
    ll ans=-INF;
    if(x<=l&&r<=y)
    {
        return a[u].sum;
    }
    pushdown(u,l,r);
    int mid=l+r>>1;
    if(x<=mid)
    {
        ans=max(ans,query(a[u].lson,l,mid));
    }
    if(y>mid)
    {
        ans=max(ans,query(a[u].rson,mid+1,r));
    }
    pushup(u);
    return ans;
} 
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main()
{
    ll n=read(),m=read();
    for(int i=1;i<=n;i++) A[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        ll op=read();
        x=read(),y=read();
        if(op==3)
        {   
            ll ans=query(1,1,n);
            cout<<ans<<endl;
        }
        else
        {
            if(op==1) flag=0;
            if(op==2) flag=1;
            ll w=read();
            update(1,1,n,w);
        }
    }
    return 0;
}

by QCurium @ 2023-09-27 16:39:50

主要原因是在pushdown的时候没将加标记下传

by kk1501201 @ 2023-09-27 18:41:16

@quchenming 谢谢大佬%%%%%%%%%%