You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
81 lines
2.0 KiB
81 lines
2.0 KiB
#include <iostream>
|
|
using namespace std;
|
|
// 第10个测试点 82ms
|
|
//快读
|
|
int read() {
|
|
int x = 0, f = 1;
|
|
char ch = getchar();
|
|
while (ch < '0' || ch > '9') {
|
|
if (ch == '-') f = -1;
|
|
ch = getchar();
|
|
}
|
|
while (ch >= '0' && ch <= '9') {
|
|
x = (x << 3) + (x << 1) + (ch ^ 48);
|
|
ch = getchar();
|
|
}
|
|
return x * f;
|
|
}
|
|
|
|
#define LL long long
|
|
const int N = 1e5 + 5;
|
|
int n, q, m;
|
|
LL tr[N << 2], tag[N << 2], sz[N << 2];
|
|
|
|
void pushup(int x) {
|
|
tr[x] = tr[x << 1] + tr[x << 1 | 1];
|
|
}
|
|
|
|
void build() {
|
|
for (m = 1; m <= n;) m <<= 1;
|
|
for (int i = 1; i <= n; i++) tr[i + m] = read();
|
|
for (int i = m; i <= (m << 1); ++i) sz[i] = 1;
|
|
for (int i = m - 1; i; i--) sz[i] = sz[i << 1] + sz[i << 1 | 1], pushup(i);
|
|
}
|
|
void addNode(int x, int v) {
|
|
tag[x] += v;
|
|
tr[x] += sz[x] * v;
|
|
}
|
|
void pushdown(int x) {
|
|
if (x ^ 1) pushdown(x >> 1);
|
|
if (tag[x]) addNode(x << 1, tag[x]), addNode(x << 1 | 1, tag[x]);
|
|
tag[x] = 0;
|
|
}
|
|
void add(int l, int r, LL v) {
|
|
pushdown((l += m - 1) >> 1), pushdown((r += m + 1) >> 1);
|
|
for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
|
|
if (~l & 1) addNode(l ^ 1, v);
|
|
if (r & 1) addNode(r ^ 1, v);
|
|
pushup(l >> 1), pushup(r >> 1);
|
|
}
|
|
for (l >>= 1; l; l >>= 1) pushup(l);
|
|
}
|
|
LL query(int l, int r) {
|
|
LL res = 0;
|
|
pushdown((l += m - 1) >> 1), pushdown((r += m + 1) >> 1);
|
|
for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
|
|
if (~l & 1) res += tr[l ^ 1];
|
|
if (r & 1) res += tr[r ^ 1];
|
|
}
|
|
return res;
|
|
}
|
|
int main() {
|
|
//文件输入输出
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("P3372.in", "r", stdin);
|
|
#endif
|
|
|
|
n = read(), q = read();
|
|
|
|
build();
|
|
|
|
while (q--) {
|
|
int a, b, c, d;
|
|
a = read(), b = read(), c = read();
|
|
if (b > c) swap(b, c);
|
|
if (a == 1)
|
|
d = read(), add(b, c, d);
|
|
else
|
|
printf("%lld\n", query(b, c));
|
|
}
|
|
return 0;
|
|
} |