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