起猛了,逛讨论区看见熟人了,顺手贴一把我的40pts代码(开发区实验中学ZYK)
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
#define int long long
const int N = 1000010;
struct Node {
int l, r;
int max, tag1, tag2;
} tr[N << 2];
int n, m, a[N];
void push_up(Node &u, Node &l, Node &r) {
u.max = max(l.max, r.max);
}
void build(int p, int l, int r) {
if(l == r) {
tr[p] = {l, r, a[l], 0, 0};
return;
}
tr[p] = {l, r, 0, 0, 0};
int mid = (l + r) >> 1;
build(2 * p, l, mid); build(2 * p + 1, mid + 1, r);
push_up(tr[p], tr[2 * p], tr[2 * p + 1]);
}
void push_down(Node &u, Node &l, Node &r) {
if(u.tag1) {
l.max = u.tag1, r.max = u.tag1;
l.tag1 = u.tag1, r.tag1 = u.tag1;
u.tag1 = 0;
} else if(u.tag2) {
l.max += u.tag2, r.max += u.tag2;
l.tag2 += u.tag2, r.tag2 += u.tag2;
u.tag2 = 0;
}
}
int query(int p, int l, int r) {
if(l <= tr[p].l && tr[p].r <= r)
return tr[p].max;
push_down(tr[p], tr[2 * p], tr[2 * p + 1]);
int mid = tr[p].l + tr[p].r >> 1, res = -1e16;
if(l <= mid) res = max(res, query(2 * p, l, r));
if(r > mid) res = max(res, query(2 * p + 1, l, r));
return res;
}
void modify1(int p, int l, int r, int k) {
if(l <= tr[p].l && tr[p].r <= r) {
if(tr[p].tag2) tr[p].tag2 = 0;
tr[p].tag1 = k;
tr[p].max = k;
return;
}
push_down(tr[p], tr[2 * p], tr[2 * p + 1]);
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid) modify1(2 * p, l, r, k);
if(r > mid) modify1(2 * p + 1, l, r, k);
push_up(tr[p], tr[2 * p], tr[2 * p + 1]);
}
void modify2(int p, int l, int r, int k) {
if(l <= tr[p].l && tr[p].r <= r) {
if(tr[p].tag1) tr[p].tag1 = 0;
tr[p].tag2 += k;
tr[p].max += k;
return;
}
push_down(tr[p], tr[2 * p], tr[2 * p + 1]);
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid) modify2(2 * p, l, r, k);
if(r > mid) modify2(2 * p + 1, l, r, k);
push_up(tr[p], tr[2 * p], tr[2 * p + 1]);
}
signed main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i ++)
scanf("%lld", &a[i]);
build(1, 1, n);
int opt, l, r, k;
while(m --) {
scanf("%lld%lld%lld", &opt, &l, &r);
if(opt == 1) {
scanf("%lld", &k);
modify1(1, l, r, k);
} else if(opt == 2) {
scanf("%lld", &k);
modify2(1, l, r, k);
} else printf("%lld\n", query(1, l, r));
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
```
by ZYK_luogu @ 2023-09-29 20:41:53