RE求调

GODTREE @ 2024-07-23 14:31:53

#include <bits/stdc++.h>
using namespace std;
#define N 10000005
int n,m,a[N];
struct tree
{
    int val,laz,l,r;
}sg[N*4];
void build(int s,int t,int p)//对[s,t]区间建立线段树，p为编号
{
    sg[p].l=s;
    sg[p].r=t;
    if (s==t)
    {
        sg[p].val=a[s];
        return ;
    }
    int mid=s+((t-s)/2);//(t+s)/2会炸int
    build(s,mid,p*2);
    build(mid+1,s,p*2+1);
    //左右建树
    sg[p].val=sg[p*2].val+sg[(p*2)+1].val;
}
void add(int l,int r,int k,int p)
{
    if (sg[p].r<l||sg[p].l>r)
    {
        return ;
    }
    if(sg[p].l>=l&&sg[p].r<=r)
    {
        sg[p].val+=(l-r+1)*k,sg[p].laz+=k;
        return ;
    }
    int mid=sg[p].l+((sg[p].l-sg[p].r)/2);
    if (sg[p].laz!=0&&l!=r)
    {
        sg[p*2].val+=sg[p].laz*(mid-l+1);
        sg[p*2+1].val+=sg[p].laz*(r-mid);
        sg[p].laz=0;
    }
    if (sg[p].l<=mid)
    {
        add(l,r,k,p*2);
    }
    else
    {
        add(l,r,k,p*2+1);
    }
    sg[p].val=sg[p*2].val+sg[p*2+1].val;
    return ;
}
int query(int l,int r,int p)
{
    if (l>=sg[p].l&&r<=sg[p].r)
    {
        return sg[p].val;
    }
    int mid=sg[p].l+((sg[p].r-sg[p].l)/2);
    if (sg[p].laz!=0)
    {
        sg[p*2].val+=sg[p].laz*(mid-l+1);
        sg[p*2+1].val+=sg[p].laz*(r-mid);
        sg[p].laz=0;
    }
    int sum=0;
    if (l<=mid)
    {
        sum+=query(l,r,p*2);
    }
    if (r>mid)
    {
        sum+=query(l,r,p*2+1);
    }
    return sum;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,n,1);
    for (int i=1;i<=m;i++)
    {
        int opt;
        cin>>opt;
        if (opt==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            add(x,y,k,1);
        }
        else
        {
            int x,y;
            cout<<query(x,y,1)<<"\n";
        }
    }
    return 0;
}

by absolute_value @ 2024-07-23 14:37:49

sg[p].val+=(l-r+1)*k,sg[p].laz+=k;

这行是不是弄错了,l-r+1会变成负数吧

by GODTREE @ 2024-07-23 15:23:22

@absolute_value 是个问题，但RE解决不了

by Mr_Dolphin @ 2024-07-23 16:55:33

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define N (int)1e6+10
int n,m,a[N];
struct tree
{
    int val,laz,l,r;
}sg[N*4];
void build(int s,int t,int p)//对[s,t]区间建立线段树，p为编号
{
    sg[p].l=s;
    sg[p].r=t;
    if (s==t)
    {
        sg[p].val=a[s];
        return ;
    }
    int mid=t+s>>1;//(t+s)/2会炸int
    build(s,mid,p*2);
    build(mid+1,t,p*2+1);
    //左右建树
    sg[p].val=sg[p*2].val+sg[(p*2)+1].val;
}
void add(int l,int r,int k,int p)
{
    if(sg[p].l>=l&&sg[p].r<=r)
    {
        sg[p].val+=(sg[p].r-sg[p].l+1)*k,sg[p].laz+=k;
        return ;
    }
    int mid=sg[p].r+sg[p].l>>1;
    if (sg[p].laz)
    {
        sg[p*2].val+=sg[p].laz*(sg[p<<1].r-sg[p<<1].l+1);
        sg[p*2+1].val+=sg[p].laz*(sg[p<<1|1].r-sg[p<<1|1].l+1);
        sg[p<<1].laz+=sg[p].laz;
        sg[p<<1|1].laz+=sg[p].laz;
        sg[p].laz=0;
    }
    if (mid>=l)
    {
        add(l,r,k,p*2);
    }
    if(mid<r)
    {
        add(l,r,k,p*2+1);
    }
    sg[p].val=sg[p*2].val+sg[p*2+1].val;
    return ;
}
int query(int l,int r,int p)
{
//  cout<<p<<' '<<sg[p].l<<' '<<sg[p].r<<' '<<l<<' '<<r<<endl;
    if (l<=sg[p].l&&r>=sg[p].r)
    {
        return sg[p].val;
    }
    int mid=sg[p].l+sg[p].r>>1;
    if (sg[p].laz)
    {
        sg[p*2].val+=sg[p].laz*(sg[p<<1].r-sg[p<<1].l+1);
        sg[p*2+1].val+=sg[p].laz*(sg[p<<1|1].r-sg[p<<1|1].l+1);
        sg[p<<1].laz+=sg[p].laz;
        sg[p<<1|1].laz+=sg[p].laz;
        sg[p].laz=0;
    }
    int sum=0;
    if (l<=mid)
    {
        sum+=query(l,r,p*2);
    }
    if (r>mid)
    {
        sum+=query(l,r,p*2+1);
    }
    return sum;
}
signed main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,n,1);
    for (int i=1;i<=m;i++)
    {
        int opt;
        cin>>opt;
        if (opt==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            add(x,y,k,1);
        }
        else
        {
            int x,y;
            cin>>x>>y;
            cout<<query(x,y,1)<<"\n";
        }
    }
    return 0;
}

by Mr_Dolphin @ 2024-07-23 16:56:00

@GODTREE

by 云翩 @ 2024-07-23 18:11:41

@GODTREE 开longlong

by GODTREE @ 2024-08-24 19:46:04

谢谢 @云翩 @Mr_Dolphin