MnZn 线段树求调

Eva_91418 @ 2024-07-17 09:29:33

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t[1145140],a[1145140],op,ret,tag[1145140],n,m;
void pushup(int x)
{
    t[x]=t[x<<1]+t[x<<1|1];
}
void build(int x,int l,int r)
{
    if(l==r)
        return t[x]=a[l],void();
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
int query(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
        return t[x];
    int mid=(l+r)>>1,ret=0;
    if(ql<=mid)
        ret+=query(x<<1,l,mid,ql,qr);
    if(qr>=mid+1)
        ret+=query(x<<1|1,mid+1,r,ql,qr);
    return ret;
    }
void apply_tag(int x,int len,int dit)
{
    t[x]+=len*dit;
    tag[x]+=dit;
}
void pushdown(int x,int l,int r)
{
    if(tag[x])
    {
        int mid=(l+r)>>1;
        apply_tag(x<<1,mid-1+1,tag[x]);
        apply_tag(x<<1|1,r-mid,tag[x]);
        tag[x]=0;   
    }
}
void change(int x,int l,int r,int cl,int cr,int dlt)
{
    pushdown(x,l,r);
    if(cl<=1&&r<=cr)
        return apply_tag(x,r-l+1,dlt);
    int mid=(l+r)>>1;
    if(cl<=mid)
        change(x<<1,l,mid,cl,cr,dlt);
    if(cr>=mid+1)
        change(x<<1|1,mid+1,r,cl,cr,dlt);
    pushup(x);
 } 
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            change(1,1,n,x,y,k);        
            //apply_tag(1,y-x+1,k);
            //pushdown(1,1,n);

        }
        else
        {
            int x,y;
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

by blue_sky_ @ 2024-07-17 10:05:28

有的 l 被写成了 1

查询时没有 pushdown

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t[1145140],a[1145140],op,ret,tag[1145140],n,m;
void pushup(int x)
{
    t[x]=t[x<<1]+t[x<<1|1];
}
void build(int x,int l,int r)
{
    if(l==r){
        t[x]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void apply_tag(int x,int len,int dit)
{
    t[x]+=len*dit;
    tag[x]+=dit;
}
void pushdown(int x,int l,int r)
{
    if(tag[x])
    {
        int mid=(l+r)>>1;
        apply_tag(x<<1,mid-l+1,tag[x]);
        apply_tag(x<<1|1,r-mid,tag[x]);
        tag[x]=0;   
    }
}
int query(int x,int l,int r,int ql,int qr)
{
    pushdown(x,l,r);
    if(ql<=l&&r<=qr)
        return t[x];
    int mid=(l+r)>>1,ret=0;
    if(ql<=mid)
        ret+=query(x<<1,l,mid,ql,qr);
    if(qr>mid)
        ret+=query(x<<1|1,mid+1,r,ql,qr);
    return ret;
    }
void change(int x,int l,int r,int cl,int cr,int dlt)
{
    pushdown(x,l,r);
    if(cl<=l&&r<=cr){
        apply_tag(x,r-l+1,dlt);
         return ;
    }
    int mid=(l+r)/2;
    if(cl<=mid)
        change(x<<1,l,mid,cl,cr,dlt);
    if(cr>mid)
        change(x<<1|1,mid+1,r,cl,cr,dlt);
    pushup(x);
 } 
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            change(1,1,n,x,y,k);        
        }
        else
        {
            int x,y;
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

by Eva_91418 @ 2024-07-17 10:12:03

@bluesky 谢谢大佬 /thk