全RE，求调！

Bramble_Marshall @ 2024-07-20 18:37:51

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct SegTree {
    int a[N * 4], d[N * 4], lzy[N * 4];

    void pud(int l, int r, int s, int t, int p) {
        int mid = s + (t - s >> 2);
        if (lzy[p])
            d[p * 2] += lzy[p] * (mid - s + 1),
            d[p * 2 + 1] += lzy[p] * (t - mid),
            lzy[p * 2] += lzy[p],
            lzy[p * 2 + 1] += lzy[p],
            lzy[p] = 0;
        if (l <= mid) pud(l, r, s, mid, p * 2);
        if (r > mid) pud(l, r, mid + 1, t, p * 2 + 1);
    }

    void build(int s, int t, int p) {
        if (s == t) {
            d[p] = a[s];
            return;
        } int mid = s + (t - s >> 2);
        if (s <= mid) build(s, mid, p * 2);
        if (t > mid) build(mid + 1, t, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }

    int read(int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) return d[p];
        int mid = s + (t - s >> 2), sum = 0;
        pud(l, r, s, t, p);
        if (l <= mid) sum += read(l, r, s, mid, p * 2);
        if (r > mid) sum += read(l, r, mid + 1, t, p * 2 + 1);
        return sum;
    }

    void add(int ad, int l, int r, int s, int t, int p) {
        if (l <= s && t <= r)
            d[p] += ad * (t - s + 1), lzy[p] += ad;
        if (s != t) pud(l, r, s, t, p);
        int mid = s + (t - s >> 2);
        if (l <= mid) add(ad, l, r, s, mid, p * 2);
        if (r > mid) add(ad, l, r, mid + 1, t, p * 2 + 1);
    }
} st;

int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> st.a[i];
    st.build(1, n, 1);
    for (int i = 1, temp, x, y, k; i <= m; i++) {
        cin >> temp;
        if (temp == 1) {
            cin >> x >> y >> k;
            st.add(k, x, y, 1, n, 1);
        } else if (temp == 2)
            cin >> x >> y,
            cout << st.read(x, y, 1, n, 1) << endl;
    }
    return 0;
}

by wild_asriel_X @ 2024-07-21 11:18:54

@Bramble_Marshall 按照正常的写法来说mid=s+(t-s>>1)（但应该也行？？？）,然后pud是不用递归的，您的add里应该也是要update的

by Bramble_Marshall @ 2024-07-21 15:32:27

@chaotic_ 还是RE???但RE应该是数组越界，我感觉找不到数组越界的地方啊

by wild_asriel_X @ 2024-07-21 17:35:14

@Bramble_Marshall 抱歉，有个第一眼就看到的错忘说了,add的第一个if里要return(悲)

by Bramble_Marshall @ 2024-07-23 10:01:59

改成这样了， @chaotic_

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m;

struct SegTree {
    int a[N], d[N * 4], lzy[N * 4];

    void build(int l, int r, int s, int t, int p) {  // Build a SegTree in [l, r], tot point is p, leads to [s, t]
        if (s == t) {
            d[p] = a[s];
            return;
        } int mid = s + (t - s >> 1);
        build(l, r, s, mid, p << 1);
        build(l, r, mid + 1, t, (p << 1) + 1);
        d[p] = d[p << 1] + d[(p << 1) + 1];
    }

    void pd(int s, int t, int p) {
        int mid = s + (t - s >> 1);
        if (lzy[p] && (p << 2) <= n)
            // cout << "Did push\n",
            d[p << 1] += lzy[p] * (mid - s + 1),
            d[(p << 1) + 1] += lzy[p] * (t - mid),
            lzy[p << 1] += lzy[p],
            lzy[(p << 1) + 1] += lzy[p];
        lzy[p] = 0;
    }

    int gets(int l, int r, int s, int t, int p) {
        // cout << "Getting Sum...\n";
        if (l <= s && t <= r) {
            // cout << "Got a lonely sum\n";  // Unpush
            return d[p];
        } // cout << "Pushing the lazy mark down...\n";
        pd(s, t, p);
        // cout << "Pushed the mark down\n";
        int mid = s + (t - s >> 1);
        int sum = 0;
        if (l <= mid) sum += gets(l, r, s, mid, p << 1);
        if (r > mid) sum += gets(l, r, mid + 1, r, (p << 1) + 1);
        // cout << "Got the sum\n";  // Unpush
        return sum;
    }

    void add(int l, int r, int s, int t, int p, int ad) {
        // cout << "Start adding...\n";
        if (l <= s && t <= r) {
            // cout << "Adding...\n";
            d[p] += ad * (t - s + 1);
            lzy[p << 1] += ad;
            lzy[(p << 1) + 1] += ad;
            return;
        } else if ((s > r || t < l) && s == t) {
            // cout << "Jump out\n";
            return;
        } pd(s, t, p);
        int mid = s + (t - s >> 1);
        if (l <= mid) add(l, r, mid + 1, t, p << 1, ad);
        if (r > mid) add(l, r, s, mid, (p << 1) + 1, ad);
        // cout << "Done\n";
        // d[p] = d[p << 1] + d[(p << 1) + 1];
    }
} st;

int main() {
    cin >> n >> m;
    memset(st.a, 0, sizeof(st.a));
    memset(st.d, 0, sizeof(st.d));
    memset(st.lzy, 0, sizeof(st.lzy));
    for (int i = 1; i <= n; i++) cin >> st.a[i];
    st.build(1, n, 1, n, 1);
    for (int i = 1; i <= m; i++) {
        int pre, x, y, k;
        cin >> pre;
        switch (pre) {
            case 1:
                cin >> x >> y >> k;
                st.add(x, y, 1, n, 1, k);
                break;
            case 2:
                cin >> x >> y;
                cout << st.gets(x, y, 1, n, 1) << endl;
        }
    }
    return 0;
}

就只是有3个RE变成WA了???

by wild_asriel_X @ 2024-07-23 17:59:32

@Bramble_Marshall 更怪了（划），首先gets的if(r>mid)里gets(l, r, mid + 1, \Large r, (p << 1) + 1);大概是gets(l, r, mid + 1, \Large t, (p << 1) + 1);

by wild_asriel_X @ 2024-07-23 18:02:00

add里面改成和gets里差不多

by wild_asriel_X @ 2024-07-23 18:02:21

记得开long long

by Bramble_Marshall @ 2024-07-23 18:35:05

@chaotic_ 还有add最后一行注释代码要写回来?现在调好了