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.
85 lines
2.4 KiB
85 lines
2.4 KiB
#include <iostream>
|
|
using namespace std;
|
|
const int N = 100010;
|
|
int n, q;
|
|
|
|
// 线段树模板
|
|
#define int long long
|
|
#define ls u << 1
|
|
#define rs u << 1 | 1
|
|
#define mid ((l + r) >> 1)
|
|
struct Node {
|
|
int l, r;
|
|
int sum, add; // 区间总和，累加懒标记
|
|
} tr[N << 2];
|
|
|
|
// 更新统计信息
|
|
void pushup(int u) {
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
}
|
|
|
|
void pushdown(int u) {
|
|
if (tr[u].add == 0) return;
|
|
tr[ls].add += tr[u].add;
|
|
tr[rs].add += tr[u].add;
|
|
tr[ls].sum += (tr[ls].r - tr[ls].l + 1) * tr[u].add;
|
|
tr[rs].sum += (tr[rs].r - tr[rs].l + 1) * tr[u].add;
|
|
tr[u].add = 0; // 清除懒标记
|
|
}
|
|
|
|
// 构建
|
|
void build(int u, int l, int r) {
|
|
tr[u].l = l, tr[u].r = r; // 标记范围
|
|
if (l == r) { // 叶子
|
|
cin >> tr[u].sum; // 区间内只有一个元素l(r),区间和为read(),不需要记录向下的传递tag
|
|
return;
|
|
}
|
|
build(ls, l, mid), build(rs, mid + 1, r); // 左右儿子构建
|
|
pushup(u); // 通过左右儿子构建后，向祖先节点反馈统计信息变化
|
|
}
|
|
|
|
// 区间所有元素加上v
|
|
void modify(int u, int L, int R, int v) {
|
|
int l = tr[u].l, r = tr[u].r;
|
|
if (l >= L && r <= R) { // 如果完整被覆盖
|
|
tr[u].sum += (r - l + 1) * v;
|
|
tr[u].add += v;
|
|
return;
|
|
}
|
|
if (l > R || r < L) return; // 如果没有交集
|
|
pushdown(u); // 下传懒标记
|
|
modify(ls, L, R, v), modify(rs, L, R, v); // 修改左，修改右
|
|
pushup(u); // 向上汇报统计信息
|
|
}
|
|
|
|
// 查询
|
|
int query(int u, int L, int R) {
|
|
int l = tr[u].l, r = tr[u].r;
|
|
if (l >= L && r <= R) return tr[u].sum; // 如果完整被覆盖
|
|
if (l > R || r < L) return 0; // 如果没有交集
|
|
pushdown(u); // 下传懒标记
|
|
return query(ls, L, R) + query(rs, L, R); // 查询左+查询右
|
|
}
|
|
|
|
signed main() {
|
|
// 文件输入输出
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("P3372.in", "r", stdin);
|
|
#endif
|
|
// 加快读入
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
cin >> n >> q;
|
|
|
|
// 构建线段树
|
|
build(1, 1, n);
|
|
|
|
while (q--) {
|
|
int op, l, r, v;
|
|
cin >> op >> l >> r;
|
|
if (op == 1)
|
|
cin >> v, modify(1, l, r, v);
|
|
else
|
|
printf("%lld\n", query(1, l, r));
|
|
}
|
|
return 0;
|
|
} |