88 lines
2.5 KiB
C++
88 lines
2.5 KiB
C++
|
/*
|
|||
|
|
题目：
|
|||
|
|
将某区间每一个数加上k
|
|||
|
|
求出某区间每一个数的和
|
|||
|
|
|
|||
|
|
题目总结：
|
|||
|
|
区间修改，区间查询
|
|||
|
|
|
|||
|
|
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
#include <iostream>
|
|||
|
|
using namespace std;
|
|||
|
|
#define LL long long
|
|||
|
|
#define N 100010
|
|||
|
|
|
|||
|
|
//快读
|
|||
|
|
LL read() {
|
|||
|
|
LL 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;
|
|||
|
|
}
|
|||
|
|
int n, q, m;
|
|||
|
|
LL tr[N << 2], tag[N << 2];
|
|||
|
|
|
|||
|
|
void build() {
|
|||
|
|
for (m = 1; m <= n;) m <<= 1;
|
|||
|
|
for (int i = 1; i <= n; i++) tr[m + i] = read();
|
|||
|
|
for (int i = m - 1; i >= 1; i--) tr[i] = tr[i << 1] + tr[i << 1 | 1];
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
void add(int l, int r, int d) {
|
|||
|
|
int lc = 0, rc = 0, c = 1;
|
|||
|
|
// 开区间，从左右叶子端点出发，如果l和r不是兄弟节点，就一路向上
|
|||
|
|
// lc 表示当前左端点走到的子树有多少个元素在修改区间内
|
|||
|
|
// rc 表示当前右端点走到的子树有多少个元素在修改区间内
|
|||
|
|
// c 当前层叶子节点个数
|
|||
|
|
for (l = m + l - 1, r = m + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1, c <<= 1) {
|
|||
|
|
tr[l] += d * lc, tr[r] += d * rc; //自底向上，更新统计信息tr和
|
|||
|
|
if (~l & 1) tag[l ^ 1] += d, tr[l ^ 1] += d * c, lc += c; // l % 2 == 0 左端点 是左儿子 右子树完整在区间内
|
|||
|
|
if (r & 1) tag[r ^ 1] += d, tr[r ^ 1] += d * c, rc += c; // r % 2 == 1 右端点 是右儿子 左子树完整在区间内
|
|||
|
|
}
|
|||
|
|
//是兄弟节点时，需要一路向上到根进行推送
|
|||
|
|
for (; l || r; l >>= 1, r >>= 1) tr[l] += d * lc, tr[r] += d * rc;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
//区间查询
|
|||
|
|
LL query(int l, int r) {
|
|||
|
|
LL lc = 0, rc = 0, c = 1;
|
|||
|
|
LL res = 0;
|
|||
|
|
for (l = m + l - 1, r = m + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1, c <<= 1) {
|
|||
|
|
if (tag[l]) res += tag[l] * lc;
|
|||
|
|
if (tag[r]) res += tag[r] * rc;
|
|||
|
|
if (~l & 1) res += tr[l ^ 1], lc += c;
|
|||
|
|
if (r & 1) res += tr[r ^ 1], rc += c;
|
|||
|
|
}
|
|||
|
|
for (; l || r; l >>= 1, r >>= 1) res += tag[l] * lc, res += tag[r] * rc;
|
|||
|
|
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();
|
|||
|
|
add(l, r, c);
|
|||
|
|
} else
|
|||
|
|
printf("%lld\n", query(l, r));
|
|||
|
|
}
|
|||
|
|
return 0;
|
|||
|
|
}
|