doublebreathing @ 2023-08-28 21:33:25
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
const int N = 2000001;
typedef long long LL;
struct node {
LL l, r, maxn, cover, add;
bool st;
} tr[N * 8];
int n, q, w[N];
void pushup(int u) {
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void pushdown1(int u) {
node &a = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
if (a.add) {
l.add += a.add, l.maxn += l.add;
r.add += a.add, r.maxn += r.add;
a.add = 0;
}
}
void pushdown2(int u) {
node &a = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
if (a.st == 1) {
l.cover = a.cover, l.maxn = a.cover;
r.cover = a.cover, r.maxn = a.cover;
l.add = r.add = a.add = 0;
a.st = 0;
}
}
void build(int u, int l, int r) {
if (l == r) {
tr[u] = {l, r, w[l], w[l], 0, 0};
return;
} else {
tr[u] = {l, r};
int mid = tr[u].l + tr[u].r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify_add(int u, int l, int r, int add) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].maxn += add;
tr[u].add += add;
} else {
pushdown1(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify_add(u << 1, l, r, add);
if (r > mid) modify_add(u << 1 | 1, l, r, add);
pushup(u);
}
}
void modify_cover(int u, int l, int r, int c) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].cover = c;
tr[u].maxn = c;
tr[u].add = 0;
tr[u].st = 1;
} else {
pushdown2(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify_cover(u << 1, l, r, c);
if (r > mid) modify_cover(u << 1 | 1, l, r, c);
pushup(u);
}
}
LL query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].maxn;
}
pushdown2(u);
pushdown1(u);
int mid = tr[u].l + tr[u].r >> 1;
LL maxx = -0x3f3f3f3f;
if (l <= mid) maxx = max(query(u << 1, l, r), maxx);
if (r > mid) maxx = max(query(u << 1 | 1, l, r), maxx);
return maxx;
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
build(1, 1, n);
while (q--) {
int op;
scanf("%d", &op);
if (op == 1) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
modify_cover(1, l, r, x);
} else if (op == 2) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
modify_add(1, l, r, x);
} else {
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, l, r));
}
}
return 0;
}by ZYK_luogu @ 2023-09-29 20:41:53
起猛了，逛讨论区看见熟人了，顺手贴一把我的40pts代码（开发区实验中学ZYK）
#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;
}