蒟蒻动态开点线段树样例没过 T^T

miss_A @ 2023-12-17 12:12:28

#include <iostream>
#include <cstdio>
#include <cctype>
#define ll unsigned long long

using namespace std;
const int N = 1e5+1;
ll n, m, tot, root;
ll d[2*N], tag[2*N], a[N];
ll ls[2*N], rs[2*N];

namespace rp {
    ll read() {
        ll x = 0, w = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') w = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            x = x * 10 + (ch - '0');
            ch = getchar();
        }
        return x * w;
    }

    void print(ll x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
}

namespace segt {
    void build(ll s, ll t, ll& p) {
        if (!p) p = ++tot;
        if (s == t) {
            d[p] = a[s];
            return ;
        }
        ll m = s + ((t - s) >> 1);
        build(s, m, ls[p]);
        build(m + 1, t, rs[p]);
        d[p] = d[ls[p]] + d[rs[p]];
    }

    void push_tag(ll &p, ll l, ll r, ll k){
        if(!p)p = ++tot;
        d[p] += k * (r - l + 1);
        tag[p] += k;
    }

    void pushdown(ll l1, ll rr, ll& p, ll l, ll r) {
        if (l1 > l || rr < r) return ;
        ll m = l + ((r - l) >> 1);
        push_tag(ls[p], l, m, tag[p]);
        push_tag(rs[p], m + 1, r, tag[p]);
        tag[p] = 0;
    }

    void update(ll l, ll r, ll k, ll s, ll t, ll& p) {
        if (!p) return ;
        if (l > t || r < s) return ;
        if (l >= s && r <= t) {
            push_tag(p, l, r, k);
            return ;
        }
        ll m = (s + ((t - s) >> 1));
        if (tag[p]) pushdown(l, r, p, s, t);
        if (l < m) update(l, r, k, s, m, ls[p]);
        if (r > m) update(l, r, k, m + 1, t, rs[p]);
        d[p] = d[ls[p]] + d[rs[p]];
    }

    ll getsum(ll l, ll r, ll s, ll t, ll& p) {
        if (l > t || r < s) return 0;
        if (l >= s && r <= t) return d[p];
        ll m = s + ((t - s) >> 1);
        if (tag[p]) pushdown(l, r, p, s, t);
        ll sum = 0;
        if (l < m) sum += getsum(l, r, s, m, ls[p]);
        if (r > m) sum += getsum(l, r, m + 1, t, rs[p]);
        return sum;
    }
}

int main() {

    //freopen("code.in", "r", stdin);
    //freopen("code.out", "w", stdout);
    ios::sync_with_stdio(false);

    n = rp::read(), m = rp::read();
    for (int i = 1; i <= n; i++) {
        ll num = rp::read();
        a[i] = num;
    }
    segt::build(1ll, n, root);

    for (int i = 1; i <= m; i++) {
        ll num = rp::read(), x = rp::read(), y = rp::read();
        if (num == 1) {
            ll k = rp::read();
            segt::update(x, y, k, 1ll, n, root);
        } else {
            ll ans = segt::getsum(x, y, 1ll, n, root);
            rp::print(ans);
            putchar('\n');
        }
    }

    return 0;
}

by Dws_t7760 @ 2023-12-17 12:50:38

@miss_A 错误有点多，先把修改过的代码给你，具体可以用代码对比器对比一下

#include <iostream>
#include <cstdio>
#include <cctype>
#define ll unsigned long long

using namespace std;
const int N = 1e5 + 1;
ll n, m, tot, root;
ll d[2 * N], tag[2 * N], a[N];
ll ls[2 * N], rs[2 * N];

namespace rp {
    ll read() {
        ll x = 0, w = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') w = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            x = x * 10 + (ch - '0');
            ch = getchar();
        }
        return x * w;
    }

    void print(ll x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
}

namespace segt {
    void build(ll s, ll t, ll& p) {
        if (!p) p = ++tot;
        if (s == t) {
            d[p] = a[s];
            return;
        }
        ll m = s + ((t - s) >> 1);
        build(s, m, ls[p]);
        build(m + 1, t, rs[p]);
        d[p] = d[ls[p]] + d[rs[p]];
    }

    void push_tag(ll& p, ll l, ll r, ll k) {
        if (!p)p = ++tot;
        d[p] += k * (r - l + 1);
        tag[p] += k;
    }

    void pushdown(ll l1, ll rr, ll& p, ll l, ll r) {
        if (l == r) return;
        ll m = l + ((r - l) >> 1);
        push_tag(ls[p], l, m, tag[p]);
        push_tag(rs[p], m + 1, r, tag[p]);
        tag[p] = 0;
    }

    void update(ll l, ll r, ll k, ll s, ll t, ll& p) {
        if (!p) return;
        if (l > t || r < s) return;
        if (l <= s && r >= t) {
            push_tag(p, s, t, k);
            return;
        }
        ll m = (s + ((t - s) >> 1));
        if (tag[p]) pushdown(l, r, p, s, t);
        if (l <= m) update(l, r, k, s, m, ls[p]);
        if (r > m) update(l, r, k, m + 1, t, rs[p]);
        d[p] = d[ls[p]] + d[rs[p]];
    }

    ll getsum(ll l, ll r, ll s, ll t, ll& p) {
        if (l > t || r < s) return 0;
        if (l <= s && r >= t) return d[p];
        ll m = s + ((t - s) >> 1);
        if (tag[p]) pushdown(l, r, p, s, t);
        ll sum = 0;
        if (l <= m) sum += getsum(l, r, s, m, ls[p]);
        if (r > m) sum += getsum(l, r, m + 1, t, rs[p]);
        return sum;
    }
}

int main() {

    //freopen("code.in", "r", stdin);
    //freopen("code.out", "w", stdout);
    ios::sync_with_stdio(false);

    n = rp::read(), m = rp::read();
    for (int i = 1; i <= n; i++) {
        ll num = rp::read();
        a[i] = num;
    }
    segt::build(1ll, n, root);

    for (int i = 1; i <= m; i++) {
        ll num = rp::read(), x = rp::read(), y = rp::read();
        if (num == 1) {
            ll k = rp::read();
            segt::update(x, y, k, 1ll, n, root);
        }
        else {
            ll ans = segt::getsum(x, y, 1ll, n, root);
            rp::print(ans);
            putchar('\n');
        }
    }

    return 0;
}

by miss_A @ 2023-12-17 20:00:24

@t7760 orz orz解决了，感谢大佬