本地编译报错,求大佬调

P3372 【模板】线段树 1

UT_MC_wuming @ 2023-08-09 19:11:37

#include <bits/stdc++.h>
using namespace std;
#define _M (st+en)/2
int arr[114514 * 4], tree[114514 * 4], n, m, k, op, x, y;//树状数组要*4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
void Build_tree(int root, int st, int en) {
    if (st == en) {
        tree[root] = arr[st];
        return;
    }
    int mid = _M;
    //cout << mid << endl;
    int l_root = 2 * root;
    int r_root = 2 * root + 1;
    Build_tree(l_root, st, mid);
    Build_tree(r_root, mid + 1, en);
    tree[root] = tree[l_root] + tree[r_root];
}
void Opt_add(int root, int st, int en, int l, int r, int num) {
    /*if (st>r || en<l)return;//剪枝,[st,en]不在[l,r]内时跳出
    if (st == en) {
        tree[root] += num;
        return;
    }
    int mid = _M;
    int l_root = 2 * root;
    int r_root = 2 * root + 1;
    Opt_add(l_root,st,mid,l,r,num);
    Opt_add(r_root,mid+1,en,l,r,num);
    tree[root] = tree[l_root] + tree[r_root];
    */
    //以上为小杯做法
    int lazy[114514*4];
    if (st > r || en < l)return;
    if (l <= st && en <= r) {
        tree[root] += (en - st + 1) * num;
        lazy[root] += num;
        return;
    }
    int mid = _M;
    if (st != en && lazy[root]) {
        tree[root * 2] += lazy[root] * (mid - st + 1);
        tree[root * 2 + 1] += lazy[root] * (en - mid);
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
        lazy[root] = 0;
    }
    if (l <= mid) Opt_add(root * 2, st, mid, l, r, num);
    if (r > mid) Opt_add(root * 2 + 1, mid + 1, en, l, r, num);
    tree[root] = tree[root * 2] + tree[root * 2 + 1];
}
int Opt_query(int root, int st, int en, int l, int r) {
    if (st > r || en < l)return 0;//剪枝,[st,en]不在[l,r]内时跳出
    if (st == en || (l <= st && en <= r)) {
        return tree[root];
    }
    int mid = _M;
    int l_root = 2 * root;
    int r_root = 2 * root + 1;
    int sum1 = Opt_query(l_root, st, mid, l, r);
    int sum2 = Opt_query(r_root, mid + 1, en, l, r);
    return sum1 + sum2;
    //你说的对但是我return l_root+r_root是**
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }Build_tree(1, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            Opt_add(1, 1, n, x, y, k);
        }
        else if (op == 2) {
            cin >> x >> y;
            cout << Opt_query(1, 1, n, x, y) << endl;
        }
    }
    return 0;
}

by emo_male_god @ 2023-08-09 19:15:02

啊?我都能直接运行啊?确定是CE不是RE?


by SF_bee @ 2023-08-09 19:19:04

数组爆内存了,尝试使用空间复杂度更低的算法


by Argvchs @ 2023-08-09 19:30:53

@SF_bee 这么小的数组还爆内存??


by SF_bee @ 2023-08-09 19:51:38

我自己试爆了


|