haha_hua @ 2022-11-20 21:08:41

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[500005],val[500005],d[500005];
char ch;

ll read(){
    ll s = 0,w = 1;
    ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <='9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}

void build(int x,int l,int r){

    if(l == r){
        a[x] = val[l];
        return ;
    }
    int mid = (l + r) / 2;
    build(2*x,l,mid);
    build(2*x+1,mid+1,r);
    a[x] = a[2*x] + a[2*x+1];
    return ;
}

void pushdown(int x,int l,int r,int mid){
    if(d[x] == 0) return ;
    d[2*x] += d[x];
    a[2*x] += d[x]*(mid - l + 1);
    d[2*x+1] += d[x];
    a[2*x+1] += d[x]*(r - mid);
    d[x] = 0;
    return ;
}

ll chax(int x,int l,int r,int el,int er){

    if(l == el && r == er){
        return a[x];
    }
    int mid = (l + r) /2;
    pushdown(x,l,r,mid);
    if(el <= mid && er > mid){
        return chax(2*x,l,mid,el,mid) + chax(2*x+1,mid+1,r,mid+1,er);
    } else if(er <= mid){
        chax(2*x,l,mid,el,er);
    } else{
        chax(2*x+1,mid+1,r,el,er);
    }

}

void xiug(int x,int l,int r,int el,int er,ll z){

    if(el == l && er == r){
        d[x] += z;
        a[x] += z*(r-l+1);
        return ;
    }
    int mid = (l + r) / 2;
    pushdown(x,l,r,mid);
    if(el <= mid && er > mid){
        xiug(2*x,l,mid,el,mid,z);
        xiug(2*x+1,mid+1,r,mid+1,er,z);
    } else if(er <= mid){
        xiug(2*x,l,mid,el,er,z);
    } else{
        xiug(2*x+1,mid+1,r,el,er,z);
    }
    return ;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        val[i] = read();
    }

    build(1,1,n);

    ll l,r,p,x;
    for(int i = 1; i <= m; i++){
        p = read(),l = read(),r = read();
        if(p == 1){
            x = read();
            xiug(1,1,n,l,r,x);  
        } 
        else{
            printf("%lld\n",chax(1,1,n,l,r));
        }
    }

    return 0;
}

by Strelitzia_ @ 2022-11-20 21:19:36

1.向下传参时，如果题目问的是 [l,r]，那么在传这两个参数时请不要改成 [l,mid] 或是 [mid+1,r]。

return chax(2*x,l,mid,el,mid) + chax(2*x+1,mid+1,r,mid+1,er);

改成：

return chax(2*x,l,mid,el,er) + chax(2*x+1,mid+1,r,el,er);

下面的 xiug() 函数同理。

2.这一行：

if(el == l && er == r){
    d[x] += z;
    a[x] += z*(r-l+1);
    return ;
}

改成：

if(el <= l && er >= r){
    d[x] += z;
    a[x] += z*(r-l+1);
    return ;
}

下面的 xing() 同理。

修改或者查询时，您只需要让这一块区间被 [l,r] 完全覆盖即可，不需要让两者完全吻合。

by haha_hua @ 2022-11-20 21:20:11

真的有点无语，发帖没几分钟，翻着题解 知道哪里错了 在修改函数( xiug() )的结尾要加

void xiug(int x,int l,int r,int el,int er,ll z){

    if(el == l && er == r){
        d[x] += z;
        a[x] += z*(r-l+1);
        return ;
    }
    int mid = (l + r) / 2;
    pushdown(x,l,r,mid);
    if(el <= mid && er > mid){
        xiug(2*x,l,mid,el,mid,z);
        xiug(2*x+1,mid+1,r,mid+1,er,z);
    } else if(er <= mid){
        xiug(2*x,l,mid,el,er,z);
    } else{
        xiug(2*x+1,mid+1,r,el,er,z);
    }
    a[x] = a[2*x] + a[2*x+1]; //就是这里...

    return ;
}

a[x] = a[2x] + a[2x+1] 浪费了我一晚上的时间在找

by TankYu @ 2022-11-20 21:20:51

建议学习一下线段树的细节

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, a[500005], val[500005], d[500005];
char ch;

ll read()
{
    ll s = 0, w = 1;
    ch = getchar();
    while (ch < '0' || ch > '9')
        {
            if (ch == '-') w = -1;
            ch = getchar();
        }
    while (ch >= '0' && ch <= '9')
        {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
    return s * w;
}

void build(int x, int l, int r)
{
    if (l == r)
        {
            a[x] = val[l];
            return ;
        }
    int mid = (l + r) / 2;
    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
    a[x] = a[2 * x] + a[2 * x + 1];
    return ;
}

void pushdown(int x, int l, int r, int mid)
{
    if (d[x] == 0) return ;
    d[2 * x] += d[x];
    a[2 * x] += d[x] * (mid - l + 1);
    d[2 * x + 1] += d[x];
    a[2 * x + 1] += d[x] * (r - mid);
    d[x] = 0;
    return ;
}

ll chax(int x, int l, int r, int el, int er)
{
    if (l >= el && r <= er)
        {
            return a[x];
        }
    int mid = (l + r) / 2;
    pushdown(x, l, r, mid);
    if (el <= mid && er > mid)
        {
            return chax(2 * x, l, mid, el, er) + chax(2 * x + 1, mid + 1, r, el, er);
        }
    else if (el <= mid)
        {
            return chax(2 * x, l, mid, el, er);
        }
    else
        {
            return chax(2 * x + 1, mid + 1, r, el, er);
        }
}

void xiug(int x, int l, int r, int el, int er, ll z)
{
    if (el <= l && er >= r)
        {
            d[x] += z;
            a[x] += z * (r - l + 1);
            return ;
        }
    int mid = (l + r) / 2;
    pushdown(x, l, r, mid);
    if (el <= mid && er > mid)
        {
            xiug(2 * x, l, mid, el, er, z);
            xiug(2 * x + 1, mid + 1, r, el, er, z);
        }
    else if (er <= mid)
        {
            xiug(2 * x, l, mid, el, er, z);
        }
    else
        {
            xiug(2 * x + 1, mid + 1, r, el, er, z);
        }
    a[x] = a[x * 2] + a[x * 2 + 1];
    return ;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        {
            val[i] = read();
        }
    build(1, 1, n);
    ll l, r, p, x;
    for (int i = 1; i <= m; i++)
        {
            p = read(), l = read(), r = read();
            if (p == 1)
                {
                    x = read();
                    xiug(1, 1, n, l, r, x);
                }
            else
                {
                    printf("%lld\n", chax(1, 1, n, l, r));
                }
        }

    return 0;
}

by haha_hua @ 2022-11-20 22:21:43

@TankYu好的，但是好像不是特别的有影响，我自己的要好理解一点，谢谢x

by haha_hua @ 2022-11-20 22:30:48

8@Strelitzia_ 谢谢