最后三个点 RE 了。
不好意思有强烈的代码风格
#include <bits/stdc++.h>
using namespace std;
namespace luosw {
namespace IO {
template < typename T >
inline T read() {
T ret = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
ret = ret * 10 + ch - '0', ch = getchar();
return ret * f;
}
template < typename T >
void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 10, len = 1;
while (y <= x) {
y *= 10;
len++;
}
while (len--) {
y /= 10;
putchar(x / y + 48);
x %= y;
}
}
template < typename T >
void write(T x, bool flag) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 10, len = 1;
while (y <= x) {
y *= 10;
len++;
}
while (len--) {
y /= 10;
putchar(x / y + 48);
x %= y;
}
if (flag)
putchar('\n');
}
} // namespace IO
namespace tools {
template < typename T >
T cmax(T a, T b) {
return max(a, b);
}
template < typename T >
T cmin(T a, T b) {
return min(a, b);
}
template < typename T >
T cgcd(T a, T b) {
return __gcd(a, b);
}
template < typename T >
T clcm(T a, T b) {
return a * b / cgcd(a, b);
}
} // namespace tools
} // namespace luosw
#define int long long
int a[100005];
#define read(t) t = luosw::IO::read< int >()
#define write(t) luosw::IO::write< int >(t, true)
class SegmentTree {
private:
int b[100005], d[100005];
public:
void build(int l, int r, int p) {
if (l == r) {
d[p] = a[l];
return;
}
int m = (l + r) / 2;
build(l, m, p * 2), build(m + 1, r, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
void update(int l, int r, int c, int s, int t, int p) {
if (l <= s && r >= t) {
d[p] += (t - s + 1) * c, b[p] += c;
return;
}
int m = (s + t) / 2;
if (b[p]) {
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m), b[p * 2] += b[p], b[p * 2 + 1] += b[p];
}
b[p] = 0;
if (l <= m)
update(l, r, c, s, m, p * 2);
if (r > m)
update(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
int getSum(int l, int r, int s, int t, int p) {
if (l <= s && t <= r)
return d[p];
int m = (s + t) >> 1;
if (b[p]) {
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p], b[p * 2 + 1] += b[p];
b[p] = 0;
}
int sum = 0;
if (l <= m)
sum = getSum(l, r, s, m, p * 2);
if (r > m)
sum += getSum(l, r, m + 1, t, p * 2 + 1);
return sum;
}
SegmentTree() {
}
SegmentTree(int l, int r, int p) {
build(l, r, p);
}
};
int n, m;
signed main() {
read(n);
read(m);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
SegmentTree t(1, n, 1);
while (m--) {
int op, a, b;
read(op);
switch (op) {
case 1: {
read(op), read(a), read(b);
t.update(op, a, b, 1, n, 1);
break;
}
case 2: {
read(a), read(b);
write(t.getSum(a, b, 1, n, 1));
break;
}
}
}
#ifdef debug
system("pause");
#endif
return 0;
}
谢谢各位!