10分求助

P3372 【模板】线段树 1

ChenYanlin_20 @ 2024-01-24 17:02:58

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int a[N];
struct code{
    int l,r;
    int ans,lai;
}xd[N];
void b(int p,int l,int r){
    xd[p].l=l,xd[p].r=r;
    if(l==r) {
        xd[p].ans=a[l];
        return ;
    }
    else{
        int mid=(l+r)/2;
        b(2*p,l,mid);
        b(2*p+1,mid+1,r);
        xd[p].ans=xd[2*p].ans+xd[2*p+1].ans;
    }
}
void qlai(int p){
    if(xd[p].lai){
        xd[p*2].ans+=xd[p].lai*(xd[p*2].r-xd[p*2].l+1);
        xd[p*2+1].ans+=xd[p].lai*(xd[p*2+1].r-xd[p*2+1].l+1);
        xd[p*2].lai=xd[p].lai;
        xd[p*2+1].lai=xd[p].lai;
        xd[p].lai=0;
    }

}
void leja(int nl,int nr,int p,int k){
    if(nl<=xd[p].l&&xd[p].r<=nr){
        xd[p].ans+=(xd[p].r-xd[p].l+1)*k;
        xd[p].lai=k;
        return;
    }
    else{
        qlai(p);
        int mid=(xd[p].l+xd[p].r)/2;
        if(nl<=mid) leja(nl,nr,p*2,k);
        if(nr>mid) leja(nl,nr,p*2+1,k);
        xd[p].ans=xd[p*2].ans+xd[p*2+1].ans;
    }
}
int qh(int nl,int nr,int p){
    if(nl<=xd[p].l&&xd[p].r<=nr)
        return xd[p].ans;
    else{
        qlai(p);
        int mid=(xd[p].l+xd[p].r)/2;
        int res=0;
        if(nl<=mid) res+=qh(nl,nr,p*2);
        if(nr>mid) res+=qh(nl,nr,p*2+1);
        return res;
    }   
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    b(1,1,n);
    while(m--){
        int a,b,c,d;
        cin>>a;
        if(a==1){
            cin>>b>>c>>d;
            leja(b,c,1,d);
        }
        else{
            cin>>b>>c;
            cout<<qh(b,c,1)<<'\n';
        }
    }
    return 0;
}

by MMXIandCCXXII @ 2024-01-24 17:27:30

@chenyanlin_20 懒标记要累加,用+=,不用=


by ChenYanlin_20 @ 2024-01-24 17:29:25

@wo2011 %%%,但不妨碍我还是错了(我是没d工的)


by MMXIandCCXXII @ 2024-01-24 17:32:35

@ChenYanlin_20 可以AC啊,我试了,是不是你没改完,27,28,36行都要改


by ChenYanlin_20 @ 2024-01-24 17:34:13

@wo2011 %%%,我是菜狗,我是菜狗,一没视力二没丁丁


by Yellow_Queen @ 2024-01-24 17:36:14

@ChenYanlin_20 6


|