|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 5e5 + 10;
|
|
|
|
|
|
// 动态开点线段树
|
|
|
#define int long long
|
|
|
#define ls tr[u].l
|
|
|
#define rs tr[u].r
|
|
|
#define mid ((l + r) >> 1)
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int sum, add;
|
|
|
} tr[N << 1];
|
|
|
|
|
|
int root, idx;
|
|
|
// 汇总统计信息
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
|
}
|
|
|
// 创建节点：节点号分配，懒标记初始化
|
|
|
void build(int &u) {
|
|
|
if (u) return;
|
|
|
u = ++idx;
|
|
|
// tr[u].add = 0;
|
|
|
}
|
|
|
|
|
|
void pushdown(int &u, int l, int r) {
|
|
|
if (tr[u].add == 0) return; // 如果没有累加懒标记，返回
|
|
|
build(ls); // 左儿子创建
|
|
|
build(rs); // 右儿子创建
|
|
|
// 懒标记下传
|
|
|
tr[ls].sum += tr[u].add * (mid - l + 1); // 区间和增加=懒标记 乘以 区间长度
|
|
|
tr[rs].sum += tr[u].add * (r - mid);
|
|
|
tr[ls].add += tr[u].add; // 加法的懒标记可以叠加
|
|
|
tr[rs].add += tr[u].add;
|
|
|
// 清除懒标记
|
|
|
tr[u].add = 0;
|
|
|
}
|
|
|
|
|
|
// 区间修改
|
|
|
void modify(int &u, int l, int r, int L, int R, int v) {
|
|
|
build(u); // 动态开点
|
|
|
|
|
|
if (l >= L && r <= R) { // 如果区间被完整覆盖
|
|
|
tr[u].add += v; // 加法的懒标记可以叠加
|
|
|
tr[u].sum += v * (r - l + 1); // 区间和增加=懒标记 乘以 区间长度
|
|
|
return;
|
|
|
}
|
|
|
if (l > R || r < L) return; // 如果没有交集
|
|
|
|
|
|
// 下传懒标记
|
|
|
pushdown(u, l, r);
|
|
|
// 分裂
|
|
|
modify(ls, l, mid, L, R, v), modify(rs, mid + 1, r, L, R, v);
|
|
|
// 汇总
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 区间查询
|
|
|
int query(int u, int l, int r, int L, int R) {
|
|
|
if (l >= L && r <= R) return tr[u].sum; // 如果完整命中，返回我的全部
|
|
|
if (l > R || r < L) return 0; // 如果与我无关,返回0
|
|
|
pushdown(u, l, r);
|
|
|
return query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R);
|
|
|
}
|
|
|
/*
|
|
|
参考答案：
|
|
|
11
|
|
|
8
|
|
|
20
|
|
|
*/
|
|
|
signed main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P3372.in", "r", stdin);
|
|
|
#endif
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
int n, m;
|
|
|
cin >> n >> m; // n个节点，m次操作
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
modify(root, 1, n, i, i, x); // 单点修改,赋初值
|
|
|
}
|
|
|
|
|
|
while (m--) {
|
|
|
int op, l, r;
|
|
|
cin >> op >> l >> r;
|
|
|
if (op == 1) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
modify(root, 1, n, l, r, x); //[l,r]区间修改为x
|
|
|
} else
|
|
|
cout << query(root, 1, n, l, r) << endl; // 区间sum和
|
|
|
}
|
|
|
return 0;
|
|
|
} |
