线段树板子求调，马蜂良好

a31325365476587687 @ 2024-03-25 00:10:14

#include <bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc (p<<1)|1
#define int long long

const int N=100005;
int a[N];
struct node{
    int l,r,add,sum;
};

node tr[4*N];

void pushup(int p)
{
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

void pushdown(int p)
{
    if(tr[p].sum!=0)
    {
        if(lc<4*N)
        {
            tr[lc].add+=tr[p].add;
            tr[lc].sum+=(tr[lc].r-tr[lc].l+1)*tr[p].add;        
        }
        if(rc<4*N)
        {
            tr[rc].add+=tr[p].add;
            tr[rc].sum+=(tr[rc].r-tr[rc].l+1)*tr[p].add;        
        }
        tr[p].add=0;
    }
}

void build(int p,int ln,int rn)
{
    tr[p].l=ln,tr[p].r=rn,tr[p].add=0;
    if(ln==rn)
    {
        tr[p].sum=a[ln];
        return;
    }
    int mid=(ln+rn)>>1;
    build(lc,ln,mid);
    build(rc,mid+1,rn);
    pushup(p);
}

int query(int p,int ln,int rn)
{
    if(tr[p].l<=ln && tr[p].r>=rn)return tr[p].sum;
    int mid=(tr[p].l+tr[p].r)>>1;
    int sumn=0;
    pushdown(p);
    if(ln<=mid)sumn+=query(lc,ln,rn);
    if(rn>=mid+1)sumn+=query(rc,ln,rn);
    return sumn;
}

void update(int p,int ln,int rn,int k)
{
    if(tr[p].l<=ln && tr[p].r>=rn)
    {
        tr[p].add+=k;
        tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
        return;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    pushdown(p);
    if(ln<=mid)update(lc,ln,rn,k);
    if(mid+1<=rn)update(rc,ln,rn,k);
    pushup(p);
}

signed main()
{
    int n,m,x,y,k,op;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    while(m--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x>>y>>k;
            update(1,x,y,k);
        }
        else
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
    return 0;
}

by syp11 @ 2024-03-25 00:21:59

改好的：

#include <bits/stdc++.h>
using namespace std;
#define lc p<<1
#define rc (p<<1)|1
#define int long long

const int N=100005;
int a[N];
struct node{
    int l,r,add,sum;
};

node tr[4*N];

void pushup(int p)
{
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

void pushdown(int p)
{
    if(tr[p].sum!=0)
    {
        if(lc<4*N)
        {
            tr[lc].add+=tr[p].add;
            tr[lc].sum+=(tr[lc].r-tr[lc].l+1)*tr[p].add;        
        }
        if(rc<4*N)
        {
            tr[rc].add+=tr[p].add;
            tr[rc].sum+=(tr[rc].r-tr[rc].l+1)*tr[p].add;        
        }
        tr[p].add=0;
    }
}

void build(int p,int ln,int rn)
{
    tr[p].l=ln,tr[p].r=rn,tr[p].add=0;
    if(ln==rn)
    {
        tr[p].sum=a[ln];
        return;
    }
    int mid=(ln+rn)>>1;
    build(lc,ln,mid);
    build(rc,mid+1,rn);
    pushup(p);
}

int query(int p,int ln,int rn)
{
    if(tr[p].l>=ln && tr[p].r<=rn)return tr[p].sum;
    int mid=(tr[p].l+tr[p].r)>>1;
    int sumn=0;
    pushdown(p);
    if(ln<=mid)sumn+=query(lc,ln,rn);
    if(rn>=mid+1)sumn+=query(rc,ln,rn);
    return sumn;
}

void update(int p,int ln,int rn,int k)
{
    if(tr[p].l >=ln && tr[p].r<=rn)
    {
        tr[p].add+=k;
        tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
        return;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    pushdown(p);
    if(ln<=mid)update(lc,ln,rn,k);
    if(mid+1<=rn)update(rc,ln,rn,k);
    pushup(p);
}

signed main()
{
    int n,m,x,y,k,op;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    while(m--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x>>y>>k;
            update(1,x,y,k);
        }
        else
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
    return 0;
}

update和query函数里面形如

if(tr[p].l >=ln && tr[p].r<=rn)

的结束条件不等号写反了 @Zhr100102

by a31325365476587687 @ 2024-03-25 10:11:09

@syp11 拜谢大佬%%%