Special_Tony @ 2023-07-28 21:04:06

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); ++ i)

# define iter(type) \
    type :: iterator

# define reg register

using namespace std;

typedef size_t st;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

ll n, m, a[100005], sum[400005], lazy[400005], op, x, y, k;

void build_tree (ll x, ll l, ll r) {

    if (l == r) {

        sum[x] = a[l];

        return ;

    }

    ll mid = l + r >> 1;

    build_tree (x << 1, l, mid), build_tree ((x << 1) + 1, mid + 1, r);

    sum[x] = sum[x << 1] + sum[(x << 1) + 1];

    return ;

}

void tamper (ll now, ll l, ll r, ll x, ll y) {

    if (l == x && r == y) {

        sum[now] += k * (r - l + 1);

        lazy[now] += k;

        return ;

    }

    ll mid = l + r >> 1;

    if (mid >= y)
        tamper (now << 1, l, mid, x, y);
    else if (mid < x)
        tamper ((now << 1) + 1, mid + 1, r, x, y);
    else
        tamper (now << 1, l, mid, x, mid), tamper ((now << 1) + 1, mid + 1, r, mid + 1, y);

    sum[now] = sum[now << 1] + sum[(now << 1) + 1];

    return ;

}

ll find (ll now, ll l, ll r, ll x, ll y) {

    if (l == x && r == y)
        return sum[now];

    ll mid = l + r >> 1;

    lazy[now << 1] += lazy[now];

    lazy[(now << 1) + 1] += lazy[now];

    sum[now << 1] += lazy[now] * (mid - l + 1);

    sum[(now << 1) + 1] += lazy[now] * (r - mid);

    lazy[now] = 0;

    if (mid >= y)
        return find (now << 1, l, mid, x, y);

    if (mid < x)
        return find ((now << 1) + 1, mid + 1, r, x, y);

    return find (now << 1, l, mid, x, mid) + find ((now << 1) + 1, mid + 1, r, mid + 1, y);

}

int main () {

    old_six

    cin >> n >> m;

    for (reg int i = 1; i <= n; ++ i)
        cin >> a[i];

    build_tree (1, 1, n);

    while (m --) {

        cin >> op >> x >> y;

        if (op < 2)
            cin >> k, tamper (1, 1, n, x, y);
        else
            cout << find (1, 1, n, x, y) << '\n';

    }

    return 0;

}

by Special_Tony @ 2023-07-28 21:40:40

此贴已转移话题：

在tamper里加上push_down就A了，求解答qwq

# include <bits/stdc++.h>

# define old_six \
    ios::sync_with_stdio (0);\
    \
    cin.tie (0);\
    \
    cout.tie (0);

# define ffor(i,name) \
    for (auto i = name.begin (); i != name.end (); ++ i)

# define iter(type) \
    type :: iterator

# define reg register

using namespace std;

typedef size_t st;

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

ll n, m, a[100005], sum[400005], lazy[400005], op, x, y, k;

void build_tree (ll x, ll l, ll r) {

    if (l == r) {

        sum[x] = a[l];

        return ;

    }

    ll mid = l + r >> 1;

    build_tree (x << 1, l, mid), build_tree ((x << 1) + 1, mid + 1, r);

    sum[x] = sum[x << 1] + sum[(x << 1) + 1];

    return ;

}

void push_down (ll x, ll mid, ll l, ll r) {

    lazy[x << 1] += lazy[x];

    lazy[(x << 1) + 1] += lazy[x];

    sum[x << 1] += lazy[x] * (mid - l + 1);

    sum[(x << 1) + 1] += lazy[x] * (r - mid);

    lazy[x] = 0;

    return ;

}

void tamper (ll now, ll l, ll r, ll x, ll y) {

    if (l == x && r == y) {

        sum[now] += k * (r - l + 1);

        lazy[now] += k;

        return ;

    }

    ll mid = l + r >> 1;

    push_down (now, mid, l, r);

    if (mid >= y)
        tamper (now << 1, l, mid, x, y);
    else if (mid < x)
        tamper ((now << 1) + 1, mid + 1, r, x, y);
    else
        tamper (now << 1, l, mid, x, mid), tamper ((now << 1) + 1, mid + 1, r, mid + 1, y);

    sum[now] = sum[now << 1] + sum[(now << 1) + 1];

    return ;

}

ll find (ll now, ll l, ll r, ll x, ll y) {

    if (l == x && r == y)
        return sum[now];

    ll mid = l + r >> 1;

    push_down (now, mid, l, r);

    if (mid >= y)
        return find (now << 1, l, mid, x, y);

    if (mid < x)
        return find ((now << 1) + 1, mid + 1, r, x, y);

    return find (now << 1, l, mid, x, mid) + find ((now << 1) + 1, mid + 1, r, mid + 1, y);

}

int main () {

    old_six

    cin >> n >> m;

    for (reg int i = 1; i <= n; ++ i)
        cin >> a[i];

    build_tree (1, 1, n);

    while (m --) {

        cin >> op >> x >> y;

        if (op < 2)
            cin >> k, tamper (1, 1, n, x, y);
        else
            cout << find (1, 1, n, x, y) << '\n';

    }

    return 0;

}

by Genius_Star @ 2023-07-28 22:14:30

@sz_mane 因为 push_down 是下传懒标记的，你这个代码里面 tamper 函数是区间加，加了懒标记之后，你如果遍历到有懒标记的点，就得先下传，如果直接更新下面的点，那么会出现错误。

by Special_Tony @ 2023-07-29 13:37:44

%%%@Genius_Star 懂了