求助【哭】

P3372 【模板】线段树 1

江宁12345678 @ 2023-03-28 21:52:02

#include<bits/stdc++.h>
using namespace std;
const int maxx=111111;
long long n,m,a[111111];
struct tree
{
    int l,r;
    long long pre,add;
};
tree t[4*maxx+2];
void bt(long long p,long long l,long long r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r)
    {
        t[p].pre=a[l];
        return;
    }
    long long mid=(l+r)/2;
    bt(p*2,1,mid);
    bt(p*2+1,mid+1,r);
    t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
void bjxc(long long p)
{
    if(t[p].add!=0)
    {
        t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p].add=0; 
    }
}
void qjxg(long long p,long long x,long long y,long long z)
{
    if(x<=t[p].l&&y>=t[p].r)
    {
        t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    bjxc(p);
    long long mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
    {
        qjxg(p*2,x,y,z);
    }
    if(y>mid)
    {
        qjxg(p*2+1,x,y,z);      
    }
    t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
long long ask(long long p,long long x,long long y)
{
    if(x<=t[p].l&&y>=t[p].r) 
    {
        return t[p].pre;
    }
    bjxc(p);
    long long mid=(t[p].l+t[p].r)/2;
    long long sum=0;
    if(x<=mid) 
    {
        sum+=ask(p*2,x,y);
    }
    if(y>mid) 
    {
        sum+=ask(p*2+1,x,y);
    }
    return sum;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    bt(1,1,n);
    for(int i=1;i<=m;i++)
    {
        long long cz;
        cin>>cz;
        if(cz==1)
        {
            long long x,y,k;
            cin>>x>>y>>k;
            qjxg(1,x,y,k);
        }
        if(cz==2)
        {
            long long x,y;
            cin>>x>>y;
            cout<<ask(1,x,y)<<endl;
        }
    }
    return 0;
}

救命!!!


by Nephren_Sakura @ 2023-03-31 11:19:39

@江宁12345678

你下传的时候左右端点不动吗?

    if(x<=mid)
    {
        qjxg(p*2,x,y,z);
    }
    if(y>mid)
    {
        qjxg(p*2+1,x,y,z);      
    }

改成

    if(x<=mid)
    {
        qjxg(p*2,x,mid,z);
    }
    if(y>mid)
    {
        qjxg(p*2+1,mid+1,y,z);      
    }

ask 同理


by Nephren_Sakura @ 2023-03-31 11:20:53

@江宁12345678

bt也错了

    bt(p*2,l,mid);
    bt(p*2+1,mid+1,r);

by 江宁12345678 @ 2023-04-03 21:49:03

@_ChthollyNephren 谢大佬!


by 江宁12345678 @ 2023-04-03 22:13:06

@_ChthollyNephren 可是x和y是修改的区间不需要变吧


by Nephren_Sakura @ 2023-04-05 12:07:49

@江宁12345678

我去,我是傻逼

我们写法不同,我在写的时候下传了当前点的左右端点


|