萌新求助,为什么会出负数啊

P3372 【模板】线段树 1

mori_ @ 2023-09-15 17:14:52

为什么用树状数组它爆longlong了,但是我用另一种query(r) - query(l - 1)的写法又过了。

//
//  Created by mori on 2023/09/01 下午2:01 星期五
//
//  P3372 【模板】线段树 1 on Luogu 
//  Coded with CLion
//  

#include <bits/stdc++.h>

using namespace std;
#define int long long

#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

int read () {
    int res = 0;
    bool f = false;
    char temp = getchar();
    for (; !isdigit(temp); temp = getchar()) f = temp == '-';
    for (; isdigit(temp); temp = getchar()) res = res * 10 + temp - '0';
    if (f) return -res;
    return res;
}

constexpr int maxn = 1e5 + 5;
int c[maxn], d[maxn], a[maxn], n, m;

#define lowbit(x) ((x) & (-x))

void modify (int x, int add) {
    for (int i = x; i <= n; i += lowbit(i)) c[i] += add, d[i] += add * (x - 1);
}

int query (int l, int r) {
    if (l > r)
        swap(l, r);
    --l;
    int x = r, res = 0;
    while (r > l) res = res + x * c[r] - d[r], r -= lowbit(r);
    x = l;
    while (l > r) res = res - x * c[l] + d[l], l -= lowbit(l);
    return res;
}

void modify (int l, int r, int add) {
    modify(l, add);
    if (r < n) modify(r + 1, -add);
}

signed main () {
    n = read(), m = read();
    rep (i, 1, n) {
        a[i] = read();
        modify(i, a[i] - a[i - 1]);
    }
    rep (i, 1, m) {
        int op = read(), l = read(), r = read();
        if (op == 1) modify(l, r, read());
        else printf("%lld\n", query(l, r));
    }
    return 0;
}

by mori_ @ 2023-09-15 17:23:44

貌似不是爆longlong好像


by IOI_AK_TLR @ 2023-10-29 10:43:23

@mori_ 最后怎么解决的?我线段树也会输出负数


by mori_ @ 2023-10-30 07:23:35

@IOI_AK_TLR 这玩意我式子推错了。你要是也错了可以发个帖问一下


by IOI_AK_TLR @ 2023-10-30 07:25:36

@mori_ 已经破案了,因为ret没开longlong


|