RE求调

yingbowen @ 2022-10-23 11:30:37

#include <bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
int n,m,a[100005],tree[400005],tag[400005];
void pushUp(int x){
    tree[x] = tree[ls]+tree[rs];
    return;
}
void down(int l,int r,int x){
    int mid=(l+r)>>1;
    if(tag[x]>0){
        tag[ls]=tag[rs]=tag[x];
        tree[ls] = (mid-l+1)*tag[ls];
        tree[rs] = (r-mid)*tag[rs];
        tag[x]=0;
    }
}
void build(int l,int r,int x){//l,r表示在a中选取哪一段范围构建线段树,x表示我现在在填tree数组的哪一个结点
    if(l==r){//如果这个范围只有1个长度就直接建
        tree[x] = a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushUp(x);
}
int query(int l,int r,int x,int ql,int qr){
    if(ql<=l && qr>=r)return tree[x];
    int mid=(l+r)>>1,ans=0;
    down(l,r,x);
    if(ql<=mid)ans+=query(l,mid,ls,ql,qr);
    if(qr>mid)ans+=query(mid+1,r,rs,ql,qr); 
    return ans;
}
void change(int l,int r,int x,int ql,int qr,int v){
    if(ql<=l&&qr>=r){
        tag[x] = v;
        tree[x] = v*(r-l+1);
        return;
    }
    down(l,r,x);
    int mid=(l+r)>>1;
    if(ql<=mid)change(l,mid,ls,ql,qr,v);
    if(qr>mid)change(mid,r,rs,ql,qr,v);
    pushUp(x);
}
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 zl=0;
        cin >> zl;
        if(zl==1){
            int x,y,z;
            cin>>x>>y>>z; 
            change(1,n,1,x,y,z);
        }else{
            int x=0,y=0;
            cin >> x >> y;
            cout << query(1,n,1,x,y) << endl;
        }
    }
}

by Nityacke @ 2022-10-23 11:59:48

@yingbowen

bug有点多，帮你改好放下面了

不开longlong见祖宗

#include <bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1|1)
#define int long long
using namespace std;
int n,m,a[100005],tree[400005],tag[400005];
void pushUp(int x){
    tree[x] = tree[ls]+tree[rs];
    return;
}
void down(int l,int r,int x){
    int mid=(l+r)>>1;
    if(tag[x]>0){
        tag[ls] += tag[x];
        tag[rs] += tag[x];
        tree[ls] += (mid-l+1)*tag[x];
        tree[rs] += (r-mid)*tag[x];
        tag[x]=0;
    }
}
void build(int l,int r,int x){//l,r表示在a中选取哪一段范围构建线段树,x表示我现在在填tree数组的哪一个结点
    if(l==r){//如果这个范围只有1个长度就直接建
        tree[x] = a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushUp(x);
}
int query(int l,int r,int x,int ql,int qr){
    if(ql<=l && qr>=r)return tree[x];
    int mid=(l+r)>>1,ans=0;
    down(l,r,x);
    if(ql<=mid)ans+=query(l,mid,ls,ql,qr);
    if(qr>mid)ans+=query(mid+1,r,rs,ql,qr); 
    return ans;
}
void change(int l,int r,int x,int ql,int qr,int v){
    if(ql<=l&&qr>=r){
        tag[x] += v;
        tree[x] += v*(r-l+1);
        return;
    }
    down(l,r,x);
    int mid=(l+r)>>1;
    if(ql<=mid)change(l,mid,ls,ql,qr,v);
    if(qr>mid)change(mid+1,r,rs,ql,qr,v);
    pushUp(x);
}
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 zl=0;
        cin >> zl;
        if(zl==1){
            int x,y,z;
            cin>>x>>y>>z; 
            change(1,n,1,x,y,z);
        }else{
            int x=0,y=0;
            cin >> x >> y;
            cout << query(1,n,1,x,y) << endl;
        }
    }
}

by yingbowen @ 2022-10-25 09:41:48

@Ethereal_shadow 谢谢