全RE，求调

Kuyohana @ 2024-07-21 11:04:20

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 1;

int a[N], n, m;

struct tree{
    int l, r;
    ll pre, add;    
}tree[4 * N];

void build(int p,int l,int r){
    tree[p].l = l;
    tree[p].r = r;
    if(l == r){
        tree[p].pre = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p * 2,l , mid);
    build(p * 2 + 1,mid + 1, r);
    tree[p].pre = tree[p * 2].pre + tree[p * 2 + 1].pre;
}

void SpreadLazy(int p){ 
    if(tree[p].add){
        tree[p * 2].pre += tree[p].add * (tree[p * 2].r - tree[p * 2].l + 1);
        tree[p * 2 + 1].pre += tree[p].add * (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1);
        tree[p * 2].add += tree[p].add;
        tree[p * 2 + 1].add = tree[p].add;
        tree[p].add = 0; 
    }
}

void query(int p,int x,int y,int z){
    if(x <= tree[p].l && y >= tree[p].r){
        tree[p].pre += ll(z) * (tree[p].r - tree[p].l + 1);
        tree[p].add += z;
        return; 
    } 
    SpreadLazy(p);
    int mid = tree[p].l + tree[p].r >> 1;
    if(x <= mid)query(p * 2,x ,y, z);
    if(y >= mid)query(p * 2 + 1,x ,y, z);
    tree[p].pre = tree[p * 2].l + tree[p * 2 + 1].pre; 
}

ll ask(int p,int x,int y){
    if(x <= tree[p].l && y >= tree[p].r)return tree[p].pre;
    SpreadLazy(p);
    int mid = tree[p].l + tree[p].r >> 1;
    ll ans = 0;
    if(x <= mid) ans += ask(p * 2,x ,y);
    if(y > mid) ans += ask(p * 2 + 1,x ,y);
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1;i <= n;i ++)cin >> a[i];
    build(1, 1, n);
    for(int i = 1;i <= m;i ++){
        int a, x, y, k;
        cin >> a;
        if(a == 1){
            cin >> x >> y >> k;
            query(1, x, y, k);
        }
        if(a == 2){
            cin >> x >> y;
            cout << ask(1, x, y) << endl;
        }
    }
    return 0;
}

by Ayxrakzil @ 2024-07-21 11:08:29

@Kuyohana 首先下放懒标记那里，tree[p * 2 + 1].add = tree[p].add;你应该不小心写错了，应该是 +=，不过应该不影响re

by Ayxrakzil @ 2024-07-21 11:09:57

@Kuyohana RE的原因是 query函数里面倒数第二行，y >= mid 应该是 y > mid

by Ayxrakzil @ 2024-07-21 11:10:17

@Kuyohana 但是变成WA了?

by wild_asriel_X @ 2024-07-21 11:11:43

@Kuyohana 貌似您的query里的update写错了，应该是 tree[p].pre = tree[p 2].pre+ tree[p 2 + 1].pre;

by Ayxrakzil @ 2024-07-21 11:11:54

@Kuyohana 破案了，query函数倒数第一行 tree[p].pre = tree[p * 2].l + tree[p * 2 + 1].pre;改成tree[p].pre = tree[p * 2].pre + tree[p * 2 + 1].pre;

这个应该也是写错了吧?

by Ayxrakzil @ 2024-07-21 11:12:29

@Kuyohana 总结，粗心错了三个细节?

by Ayxrakzil @ 2024-07-21 11:13:12

草，为什么emoji打出来是问号

by quanquhengzhezou @ 2024-07-21 11:13:22

query 函数中的 tree[p].pre 更新逻辑。

SpreadLazy 函数中对右子树 add 的处理。

确保了所有数组访问在有效范围内，并且 build 函数和其他操作不会引发越界。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e7 + 10;

int a[N], n, m;

struct tree {
    int l, r;
    ll pre, add;
} tree[4 * N];

void build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    if (l == r) {
        tree[p].pre = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    tree[p].pre = tree[p * 2].pre + tree[p * 2 + 1].pre;
}

void SpreadLazy(int p) {
    if (tree[p].add) {
        tree[p * 2].pre += tree[p].add * (tree[p * 2].r - tree[p * 2].l + 1);
        tree[p * 2 + 1].pre += tree[p].add * (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1);
        tree[p * 2].add += tree[p].add;
        tree[p * 2 + 1].add += tree[p].add;  // 修改为累加
        tree[p].add = 0;
    }
}

void query(int p, int x, int y, int z) {
    if (x <= tree[p].l && y >= tree[p].r) {
        tree[p].pre += ll(z) * (tree[p].r - tree[p].l + 1);
        tree[p].add += z;
        return;
    }
    SpreadLazy(p);
    int mid = tree[p].l + tree[p].r >> 1;
    if (x <= mid) query(p * 2, x, y, z);
    if (y > mid) query(p * 2 + 1, x, y, z);
    tree[p].pre = tree[p * 2].pre + tree[p * 2 + 1].pre;  // 修正这里
}

ll ask(int p, int x, int y) {
    if (x <= tree[p].l && y >= tree[p].r) return tree[p].pre;
    SpreadLazy(p);
    int mid = tree[p].l + tree[p].r >> 1;
    ll ans = 0;
    if (x <= mid) ans += ask(p * 2, x, y);
    if (y > mid) ans += ask(p * 2 + 1, x, y);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            query(1, x, y, k);
        } else if (op == 2) {
            cin >> x >> y;
            cout << ask(1, x, y) << endl;
        }
    }
    return 0;
}

by quanquhengzhezou @ 2024-07-21 11:13:48

@Kuyohana 这样就AC了

by Kuyohana @ 2024-07-21 11:14:33

十分感谢各位！