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.
93 lines
2.1 KiB
93 lines
2.1 KiB
#include <iostream>
|
|
/*
|
|
第10个测试点 60ms/2.71MB
|
|
*/
|
|
using namespace std;
|
|
#define LL long long
|
|
|
|
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;
|
|
}
|
|
|
|
const int N = 1e5 + 10;
|
|
|
|
int n, q, h, m;
|
|
LL sum[N << 1], tag[N << 1];
|
|
|
|
void build() {
|
|
for (h = 1; 1 << h < n;) h++;
|
|
for (int i = n + 1; i <= 2 * n; i++) sum[i] = read();
|
|
for (int i = n; i; i--) sum[i] = sum[i << 1] + sum[i << 1 | 1];
|
|
}
|
|
|
|
void add(int x, int val, int len) {
|
|
sum[x] += val * len;
|
|
if (x <= n) tag[x] += val;
|
|
}
|
|
|
|
void pushup(int x) {
|
|
int len = 1;
|
|
while (x > 1) len <<= 1, x >>= 1, sum[x] = sum[x << 1] + sum[x << 1 | 1] + tag[x] * len;
|
|
}
|
|
|
|
void pushdown(int x) {
|
|
for (int i = h, len = 1 << (h - 1); i; i--, len >>= 1) {
|
|
int y = x >> i;
|
|
if (tag[y]) {
|
|
add(y << 1, tag[y], len), add(y << 1 | 1, tag[y], len);
|
|
tag[y] = 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
void modify(int l, int r, int val) {
|
|
l += n, r += n;
|
|
int yl = l, yr = r;
|
|
for (int len = 1; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1, len <<= 1) {
|
|
if (l & 1) add(l, val, len);
|
|
if (r & 1 ^ 1) add(r, val, len);
|
|
}
|
|
pushup(yl), pushup(yr);
|
|
}
|
|
|
|
LL query(int l, int r) {
|
|
l += n, r += n;
|
|
pushdown(l), pushdown(r);
|
|
LL res = 0;
|
|
for (; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
|
|
if (l & 1) res += sum[l];
|
|
if (r & 1 ^ 1) res += sum[r];
|
|
}
|
|
return res;
|
|
}
|
|
|
|
int main() {
|
|
//文件输入输出
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("P3372.in", "r", stdin);
|
|
#endif
|
|
n = read(), q = read();
|
|
|
|
build();
|
|
|
|
for (int i = 1; i <= q; i++) {
|
|
int op = read();
|
|
int l = read(), r = read();
|
|
if (op == 1) {
|
|
int c = read();
|
|
modify(l, r, c);
|
|
} else
|
|
printf("%lld\n", query(l, r));
|
|
}
|
|
return 0;
|
|
} |