求大佬看看,help

P3372 【模板】线段树 1

ljx_gkx @ 2023-03-29 14:21:51

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N =  1e5 + 10;
int w[N];
struct Node{
    int l, r;
    LL dt, sum;
}tr[N*4];

int n, m;

void pushup(int u)
{
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void pushdown(int u)
{
    auto &rt = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];
    if (rt.dt)
    {
        left.dt += rt.dt, left.sum += (left.r - left.l + 1)*rt.dt;
        right.dt += rt.dt, right.sum += (right.r - right.l + 1)*rt.dt;
        rt.dt = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l==r) {
        tr[u].sum = w[r];
        return  ;
    }

    int mid = l + r >> 1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
    pushup(u);
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r-tr[u].l+1)*k;
        tr[u].dt += k;
        return ;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l<=mid) modify(u<<1, l, r, k);
    if (r<mid) modify(u<<1|1, l, r, k);
    pushup(u);
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    pushdown(u);
    int mid = tr[u].r + tr[u].l >> 1;
    LL res=0;
    if (l <= mid) res += query(u<<1, l, r);
    if (r > mid) res += query(u<<1|1, l, r);
    return res;
}

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

    build(1, 1, n);

    while (m --)
    {
        int op, l, r, k;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> k;
            modify(1, l, r, k);
        }
        else {
            cout << query(1, l, r) << endl;
        }
    }

    return 0;
}

by SmallBlack @ 2023-03-29 14:43:37


by tidongCrazy @ 2023-03-29 14:43:55

@ljx52lm modify里面改成if(r>mid)


by ljx_gkx @ 2023-03-29 14:53:29

@tidongCrazy 谢谢大佬。我粗心了!


by ljx_gkx @ 2023-03-29 14:53:47

@SmallBlack 谢谢大佬,我粗心了!


|