Unino @ 2023-09-30 22:07:42
为啥 #10 会 RE(提交记录)
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MAX_N = 1E6 + 5;
constexpr int INF = 0x7F7F7F7F7F7F7F7F;
struct SegmentTree {
int l, r;
int rmx, tag1, tag2;
} tree[MAX_N << 2];
int n, q, a[MAX_N];
#define lson p << 1
#define rson p << 1 | 1
void pushup(int p) {
tree[p].rmx = max(tree[lson].rmx, tree[rson].rmx);
}
void pushdown1(int p) {
if (tree[p].tag1 != INF) {
tree[lson].rmx = tree[rson].rmx = tree[p].tag1;
tree[lson].tag1 = tree[rson].tag1 = tree[p].tag1;
tree[lson].tag2 = tree[rson].tag2 = 0;
tree[p].tag1 = INF;
}
}
void pushdown2(int p) {
if (tree[p].tag2 != 0) {
pushdown1(p);
tree[lson].rmx += tree[p].tag2;
tree[rson].rmx += tree[p].tag2;
tree[lson].tag2 += tree[p].tag2;
tree[rson].tag2 += tree[p].tag2;
tree[p].tag2 = 0;
}
}
void build(int p, int l, int r) {
tree[p].l = l, tree[p].r = r;
tree[p].tag1 = INF, tree[p].tag2 = 0;
if (l == r) {
tree[p].rmx = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(p);
}
void change(int p, int l, int r, int v) {
if (l <= tree[p].l && r >= tree[p].r) {
tree[p].tag1 = v;
tree[p].tag2 = 0;
tree[p].rmx = v;
return;
}
pushdown1(p), pushdown2(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) change(lson, l, r, v);
if (r > mid) change(rson, l, r, v);
pushup(p);
}
void add(int p, int l, int r, int v) {
if (l <= tree[p].l && r >= tree[p].r) {
pushdown1(p);
tree[p].tag2 += v;
tree[p].rmx += v;
return;
}
pushdown1(p), pushdown2(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) add(lson, l, r, v);
if (r > mid) add(rson, l, r, v);
pushup(p);
}
int query(int p, int l, int r) {
if (l <= tree[p].l && r >= tree[p].r) {
return tree[p].rmx;
}
pushdown1(p), pushdown2(p);
int mid = (tree[p].l + tree[p].r) >> 1;
int ans = -INF;
if (l <= mid) ans = max(ans, query(lson, l, r));
if (r > mid) ans = max(ans, query(rson, l, r));
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
while (q--) {
int op, l, r, x;
cin >> op >> l >> r;
if (op == 1) {
cin >> x;
change(1, l, r, x);
} else if (op == 2) {
cin >> x;
add(1, l, r, x);
} else {
cout << query(1, l, r) << "\n";
}
}
return 0;
}
by Failure_Terminator @ 2023-09-30 22:16:01
void add(int p, int l, int r, int v) {
if (l <= tree[p].l && r >= tree[p].r) {
//pushdown1(p);
tree[p].tag2 += v;
tree[p].rmx += v;
return;
}
pushdown1(p), pushdown2(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) add(lson, l, r, v);
if (r > mid) add(rson, l, r, v);
pushup(p);
}
不太懂这里为什么要 pushdown,删掉就对了。
by Failure_Terminator @ 2023-09-30 22:16:18
@Unino
by Unino @ 2023-10-01 07:07:38
@haimo_qwq thx%%%,这里更新时可能是叶子节点,没有
by Unino @ 2023-10-01 07:25:04
void pushdown1(int p) {
if (tree[p].tag1 != INF && lson < (n << 2) && rson < (n << 2)) {
tree[lson].rmx = tree[rson].rmx = tree[p].tag1;
tree[lson].tag1 = tree[rson].tag1 = tree[p].tag1;
tree[lson].tag2 = tree[rson].tag2 = 0;
tree[p].tag1 = INF;
}
}