几近疯癫

zh1221_qwq @ 2023-06-21 15:22:29

#include<iostream>
#define int long long
using namespace std;
const int N=1e5+5;
long long n,m,k[N],ans,t=1;
struct node{
    int l,r,sum,tag;
}a[4*N];
void build(int l,int r,int u){
    if(l==r){
        a[u].sum=k[l];
        return;
    }
    long long mid=(l+r)/2;
    a[u].l=++t;
    build(l,mid,a[u].l);
    a[u].r=++t;
    build(mid+1,r,a[u].r);
    a[u].sum=a[a[u].r].sum+a[a[u].l].sum;
}
void pushup(int u){
    a[u].sum=a[a[u].l].sum+a[a[u].r].sum;
}
void pushdown(int l,int r,int u){
    int mid=(l+r)/2;
    a[a[u].l].sum+=(mid-l+1)*a[u].tag;
    a[a[u].r].sum+=(r-mid)*a[u].tag;
    a[a[u].l].tag=a[u].tag;
    a[a[u].r].tag=a[u].tag;
    a[u].tag=0;
}
void update(int l,int r,int lc,int rc,int u,int w){
    if(l==lc&&r==rc){
        a[u].sum+=(r-l+1)*w;
        a[u].tag+=w;
        return;
    }
    int mid=(l+r)/2;
    pushdown(l,r,u);
    if(rc<=mid)update(l,mid,lc,rc,a[u].l,w);
    else if(lc>mid)update(mid+1,r,lc,rc,a[u].r,w);
    else {
        update(l,mid,lc,mid,a[u].l,w);
        update(mid+1,r,mid+1,rc,a[u].r,w);
    }
    pushup(u);
}
void query(int l,int r,int lc,int rc,int u){
    if(l==lc&&r==rc){
        ans+=a[u].sum;
        return;
    }
    int mid=(l+r)/2;
    if(rc<=mid)query(l,mid,lc,rc,a[u].l);
    else if(lc>mid)query(mid+1,r,lc,rc,a[u].r);
    else {
        query(l,mid,lc,mid,a[u].l);
        query(mid+1,r,mid+1,rc,a[u].r);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>k[i];
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int tot;
        cin>>tot;
        if(tot==1){
            int l,r,w;
            cin>>l>>r>>w;
            update(1,n,l,r,1,w);
        }
        else {
            int l,r;
            cin>>l>>r;
            query(1,n,l,r,1);
            cout<<ans<<endl;
            ans=0;
        }
    }
}

by w20230071_QwQ @ 2023-06-21 15:28:39

@zh1221_qwq 样例没过，用洛谷IDE 试试

by Liuyuzhuo @ 2023-06-21 15:28:48

@zh1221_qwq 首先你查询时要加pushdown ，然后应该还有问题

by Liuyuzhuo @ 2023-06-21 15:30:29

pushdown 里 tag 是加等于

by zh1221_qwq @ 2023-06-21 15:30:45

#include<iostream>
#define int long long
using namespace std;
const int N=1e5+5;
long long n,m,k[N],ans,t=1;
struct node{
    int l,r,sum,tag;
}a[4*N];
void build(int l,int r,int u){
    if(l==r){
        a[u].sum=k[l];
        return;
    }
    long long mid=(l+r)/2;
    a[u].l=++t;
    build(l,mid,a[u].l);
    a[u].r=++t;
    build(mid+1,r,a[u].r);
    a[u].sum=a[a[u].r].sum+a[a[u].l].sum;
}
void pushup(int u){
    a[u].sum=a[a[u].l].sum+a[a[u].r].sum;
}
void pushdown(int l,int r,int u){
    int mid=(l+r)/2;
    a[a[u].l].sum+=(mid-l+1)*a[u].tag;
    a[a[u].r].sum+=(r-mid)*a[u].tag;
    a[a[u].l].tag=a[u].tag;
    a[a[u].r].tag=a[u].tag;
    a[u].tag=0;
}
void update(int l,int r,int lc,int rc,int u,int w){
    if(l==lc&&r==rc){
        a[u].sum+=(r-l+1)*w;
        a[u].tag+=w;
        return;
    }
    int mid=(l+r)/2;
    pushdown(l,r,u);
    if(rc<=mid)update(l,mid,lc,rc,a[u].l,w);
    else if(lc>mid)update(mid+1,r,lc,rc,a[u].r,w);
    else {
        update(l,mid,lc,mid,a[u].l,w);
        update(mid+1,r,mid+1,rc,a[u].r,w);
    }
    pushup(u);
}
void query(int l,int r,int lc,int rc,int u){
    if(l==lc&&r==rc){
        ans+=a[u].sum;
        return;
    }
    int mid=(l+r)/2;
    pushdown(l,r,u);
    if(rc<=mid)query(l,mid,lc,rc,a[u].l);
    else if(lc>mid)query(mid+1,r,lc,rc,a[u].r);
    else {
        query(l,mid,lc,mid,a[u].l);
        query(mid+1,r,mid+1,rc,a[u].r);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>k[i];
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int tot;
        cin>>tot;
        if(tot==1){
            int l,r,w;
            cin>>l>>r>>w;
            update(1,n,l,r,1,w);
        }
        else {
            int l,r;
            cin>>l>>r;
            query(1,n,l,r,1);
            cout<<ans<<endl;
            ans=0;
        }
    }
}

新的,还是0分

by zh1221_qwq @ 2023-06-21 15:31:22

@Liuyuzhuo 感谢巨佬%%%%%%%%%

by Liuyuzhuo @ 2023-06-21 15:31:24

另外你这码风有点奇怪，建议换种线段树写法

by zh1221_qwq @ 2023-06-21 15:31:51

@Liuyuzhuo 关注了

by hjqhs @ 2023-06-21 15:37:26

@Liuyuzhuo 没有很奇怪吧 只是写了动态开店 还有处理左右子树时处理烦了

by hjqhs @ 2023-06-21 15:37:44

@hjqhs 动态开点

by Xy_top @ 2023-06-21 17:06:22

@zh1221_qwq pushdown 的时候左右儿子 tag 应该是加等于父亲的 tag