0分求助

P3372 【模板】线段树 1

511_Juruo_wyk @ 2024-10-13 10:34:41

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int a[N],tree[N<<2],lazy[N<<2],n,m,op,l,r,k;
void build(int i,int l,int r){
    if(l==r){
        tree[i]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i]=tree[i<<1]+tree[i<<1|1];
}
void spread(int i,int x,int y){
    int mid=l+r>>1;
    lazy[i<<1]+=lazy[i];
    tree[i<<1]+=lazy[i]*(mid-l+1); 
    lazy[i<<1|1]+=lazy[i];
    tree[i<<1|1]+=lazy[i]*(r-mid);
    lazy[i]=0;
}
void tag(int i,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        lazy[i]+=v;
        tree[i]+=v*(r-l+1);
        return;
    }
    spread(i,l,r);
    int mid=l+r>>1;
    if(x<=mid)tag(i<<1,l,mid,x,y,v);
    if(y>mid)tag(i<<1|1,mid+1,r,x,y,v);
    tree[i]=tree[i<<1]+tree[i<<1|1];
}
int ask(int i,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tree[i];
    int mid=l+r>>1,ans=0;
    spread(i,l,r);
    if(x<=mid)ans+=ask(i<<1,l,mid,x,y);
    if(y>mid)ans+=ask(i<<1|1,mid+1,r,x,y);
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld %lld %lld",&l,&r,&k);
            tag(1,1,n,l,r,k); 
        }
        else{
            scanf("%lld %lld",&l,&r);
            cout<<ask(1,1,n,l,r)<<'\n'; 
        }
    }
    return 0;
}

顺便提供我下载的测试数据1

in:

8 10
640 591 141 307 942 58 775 133 
2 1 5
2 3 8
2 3 6
2 5 8
2 4 8
1 4 8 60
2 1 6
2 5 8
1 3 7 15
1 2 6 86

out:

by masonxiong @ 2024-10-13 10:41:26

@511_Juruo_wyk

《使用 %lld 读入 int》

这会出问题的吧。

by masonxiong @ 2024-10-13 10:42:02

@511_Juruo_wyk

但其实真正的问题是，您的 spread 函数中传入的左端点是 x,y 而您用的是全局变量 l,r。

by da_ke @ 2024-10-13 10:44:52

@511_Juruo_wyk

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int a[N],tree[N<<2],lazy[N<<2],n,m;

void build(int i,int l,int r)
{
    if(l==r){
        tree[i]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i]=tree[i<<1]+tree[i<<1|1];
}

void spread(int i,int l,int r){
    int mid=(l+r)>>1;
    lazy[i<<1]+=lazy[i];
    tree[i<<1]+=lazy[i]*(mid-l+1); 
    lazy[i<<1|1]+=lazy[i];
    tree[i<<1|1]+=lazy[i]*(r-mid);
    lazy[i]=0;
}
void tag(int i,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        lazy[i]+=v;
        tree[i]+=v*(r-l+1);
        return;
    }
    spread(i,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)tag(i<<1,l,mid,x,y,v);
    if(y>mid)tag(i<<1|1,mid+1,r,x,y,v);
    tree[i]=tree[i<<1]+tree[i<<1|1];
}
int ask(int i,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tree[i];
    int mid=(l+r)>>1,ans=0;
    spread(i,l,r);
    if(x<=mid)ans+=ask(i<<1,l,mid,x,y);
    if(y>mid)ans+=ask(i<<1|1,mid+1,r,x,y);
    return ans;
}
signed main(){
    int op,l,r,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld %lld %lld",&l,&r,&k);
            tag(1,1,n,l,r,k); 
        }
        else{
            scanf("%lld %lld",&l,&r);
            cout<<ask(1,1,n,l,r)<<'\n'; 
        }
    }
    return 0;
}

不要乱在外面定义变量，spread 变量冲突了。

by da_ke @ 2024-10-13 10:45:38

@511_Juruo_wyk 另外，那个 mid=l+r>>1 最好写成 mid=l+((r-l)>>1);

by 511_Juruo_wyk @ 2024-10-13 10:50:25

@masonxiong @da_ke 谢谢，懂了

但是 #define int long long 应该对于“%lld 读入 int”和“l+r>>1 \to l+((r-l)>>1)”没什么影响吧？

by da_ke @ 2024-10-13 10:53:29

@511_Juruo_wyk 也对，但是 l+r>>1 不如 (l+r)>>1，因为 -Wall 报警告。

by masonxiong @ 2024-10-13 11:28:24

@511_Juruo_wyk

关于第一个问题，我先道个歉，我没看到上面的 #define int long long（

关于第二个问题，改后可以防计算过程溢出，但是没必要。