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

P3372 【模板】线段树 1

@[miss_A](/user/747717) 错误有点多,先把修改过的代码给你,具体可以用代码对比器对比一下 ```cpp #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 Dws_t7760 @ 2023-12-17 12:50:38


@[t7760](/user/776962) orz orz解决了,感谢大佬
by miss_A @ 2023-12-17 20:00:24


|