```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[10000005];
struct Node {
int l, r, sum, tag1, tag2;
bool flag;
} tree[10000005];
void Push_up (int p) {
tree[p].sum = max (tree[p * 2].sum, tree[p * 2 + 1].sum);
}
void Build (int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
tree[p].sum = -214748364700;
if (l == r) {
tree[p].sum = a[l];
return ;
}
int mid = (l + r) / 2;
Build (p * 2, l, mid);
Build (p * 2 + 1, mid + 1, r);
Push_up(p);
}
void Push_down (int p) {
if (tree[p].flag) {
tree[p * 2].tag1 = tree[p].tag1;
tree[p * 2 + 1].tag1 = tree[p].tag1;
tree[p * 2].tag2 = tree[p].tag2;
tree[p * 2 + 1].tag2 = tree[p].tag2;
tree[p * 2].sum = tree[p].tag1 + tree[p].tag2;
tree[p * 2 + 1].sum = tree[p].tag1 + tree[p].tag2;
tree[p * 2].flag = tree[p * 2 + 1].flag = 1;
} else {
tree[p * 2].tag2 += tree[p].tag2;
tree[p * 2 + 1].tag2 += tree[p].tag2;
tree[p * 2].sum += tree[p].tag2;
tree[p * 2 + 1].sum += tree[p].tag2;
}
tree[p].flag = tree[p].tag1 = tree[p].tag2 = 0;
}
void Update1 (int p, int L, int R, int x) {
if (L <= tree[p].l && tree[p].r <= R) {
tree[p].tag1 = x;
tree[p].tag2 = 0;
tree[p].sum = x;
tree[p].flag = 1;
return ;
}
Push_down(p);
int mid = (tree[p].l + tree[p].r) / 2;
if (L <= mid) Update1 (p * 2, L, R, x);
if (R > mid) Update1 (p * 2 + 1, L, R, x);
Push_up(p);
}
void Update2 (int p, int L, int R, int x) {
if(L <= tree[p].l && tree[p].r <= R) {
tree[p].tag2 += x;
tree[p].sum += x;
return ;
}
Push_down(p);
int mid = (tree[p].l + tree[p].r) / 2;
if (L <= mid) Update1 (p * 2, L, R, x);
if (R > mid) Update1 (p * 2 + 1, L, R, x);
Push_up(p);
}
int Query (int p, int L, int R) {
if (L <= tree[p].l && tree[p].r <= R) return tree[p].sum;
Push_down (p);
int mid = (tree[p].l + tree[p].r) / 2;
int res = -2147483647000;
if (L <= mid) res = max (res, Query (p * 2, L, R));
if (R > mid) res = max (res, Query (p * 2 + 1, L, R));
return res;
}
signed main () {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
Build (1, 1, n);
while (m--) {
int op, l, r, k;
cin >> op >> l >> r;
if (op == 1) {
cin >> k;
Update1 (1, l, r, k);
}
if (op == 2) {
cin >> k;
Update2 (1, l, r, k);
}
else cout << Query (1, l, r) << '\n';
}
return 0;
}
```
by kaceqwq @ 2022-08-17 08:05:27
@[kaceqwq](/user/527992) sum 和最大值不能放一起啊?
您这代码我直接蒙了。
by JackMerryYoung @ 2022-08-17 08:10:38
数组开小了,四倍空间。`while` 循环里面把第二个 `if` 改为 `else if`
by Micnation_AFO @ 2022-08-17 08:10:57
@[JackMerryYoung](/user/224558) 他这个估计是把 `sum` 当成 `dat` 直接用了
by Micnation_AFO @ 2022-08-17 08:11:37
@[Leap_hash_jperm](/user/574944) 可我是 1e7 唉
by kaceqwq @ 2022-08-17 08:12:21
@[Leap_hash_jperm](/user/574944) 所以错了呀,求和是 sum, 最大值怎么也是 sum???
by JackMerryYoung @ 2022-08-17 08:14:07
@[kaceqwq](/user/527992) 抱歉,没看清楚
另外,`push_down` 下传 `tag2` 的时候,由于是区间推平,`t[p * 2]` 和 `t[p * 2 + 1]` 的 `tag1` 应该赋值为 $0$,表示加 $0$。
by Micnation_AFO @ 2022-08-17 08:14:51
@[JackMerryYoung](/user/224558) 你看他的`push_up`,就是最大值
by Micnation_AFO @ 2022-08-17 08:15:46
而且 `push_down` 里面也没有必要 `else` 吧
by Micnation_AFO @ 2022-08-17 08:18:09
@[Leap_hash_jperm](/user/574944) 又不是求和的最大值。
by JackMerryYoung @ 2022-08-17 08:20:05