10分，线段树，求助

GLESENA @ 2023-08-04 10:19:36

8 10
659 463 793 740 374 330 772 681 
1 5 8 39
2 5 8
1 3 6 3
1 5 8 90
1 1 5 21
2 3 8
1 3 8 17
1 4 7 52
2 2 6
1 2 7 41

2313
4281
3278

2313
4203
3152

#include<bits/stdc++.h>
using namespace std;
#define lc i<<1
#define rc i<<1|1
#define mid (l+r)/2
int inPut[100000+1];
struct tree{
    int l,r,sum,lazytag;
}t[100000001];
void push_down(int i)
{
    t[lc].lazytag+=t[i].lazytag;
    t[rc].lazytag+=t[i].lazytag;
    t[lc].sum+=t[i].lazytag*(t[lc].r-t[lc].l+1);
    t[rc].sum+=t[i].lazytag*(t[rc].r-t[rc].l+1);
    t[i].lazytag=0;
}
void build(int i,int l,int r)
{
    t[i].l=l;t[i].r=r;
    if(l==r)
    {
        t[i].sum=inPut[l];
        return ;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    t[i].sum=t[lc].sum+t[rc].sum;
}
int search(int i,int l,int r)
{
    //cout<<t[i].l<<" "<<t[i].r<<' '<<l<<' '<<r<<'\n';
    if(l<=t[i].l&&r>=t[i].r)
    {
        return t[i].sum;
    }
    if(l>t[i].r||r<t[i].l)
    {
        return 0;
    }
    int rtrn=0;
    push_down(i);
    if(l<=t[lc].r)
    {
        rtrn+=search(lc,l,r);
    }
    if(r>=t[rc].l)
    {
        rtrn+=search(rc,l,r);
    }
    return rtrn;
}
void add(int i,int l,int r,int k)
{
    if(l<=t[i].l&&r>=t[i].r)
    {
        t[i].lazytag=k;
        t[i].sum+=(t[i].r-t[i].l+1)*t[i].lazytag;
        return ;
    }
    push_down(i);
    if(l<=t[lc].r)
    {
        add(lc,l,r,k);
    }
    if(r>=t[rc].l)
    {
        add(rc,l,r,k);
    }
    t[i].sum=t[lc].sum+t[rc].sum;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&inPut[i]);
    }
    build(1,1,n);
    int op,x,y,k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(1,x,y,k);
        }
        if(op==2)
        {
            scanf("%d%d",&x,&y);
            cout<<search(1,x,y)<<endl;
        }
    }
    return 0;
}

by LinGxIao_0230 @ 2023-08-04 10:48:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+2;
int n,m;
ll a[N],ans[N<<2],tag[N<<2];
inline int left_son(int x){return x<<1;}
inline int right_son(int x){return x<<1|1;}
inline void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",a+i);
}
inline void push_up(ll p){
    ans[p]=ans[left_son(p)]+ans[right_son(p)];
}
void build(ll p,ll l,ll r){
    tag[p]=0;
    if(l==r){
        ans[p]=a[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(left_son(p),l,mid);
    build(right_son(p),mid+1,r);
    ans[p]=ans[left_son(p)]+ans[right_son(p)];
}
inline void f(ll p,ll l,ll r,ll k){
    tag[p]+=k;
    ans[p]+=k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r){
    ll mid=(l+r)>>1;
    f(left_son(p),l,mid,tag[p]);
    f(right_son(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k){
    if(nl<=l&&r<=nr){
        f(p,l,r,k);
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid) update(nl,nr,l,mid,left_son(p),k);
    if(mid<nr) update(nl,nr,mid+1,r,right_son(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid) res+=query(q_x,q_y,l,mid,left_son(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,right_son(p));
    return res;
}
int main(){
    init();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int k;
        scanf("%d",&k);
        if(k==1){
            int l,r;
            ll s;
            scanf("%d%d%lld",&l,&r,&s);
            update(l,r,1,n,1,s);
        }
        else{
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(l,r,1,n,1));
        }
    }
    return 0;
}

by Untitled10032 @ 2023-08-04 10:51:52

line 57 & 58:

t[i].lazytag+=k;
t[i].sum+=(t[i].r-t[i].l+1)*k;