Peter_0327 @ 2024-02-02 16:10:49
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5, INF = 0x3f3f3f3f;
long long n, q, op, l, r, x, a[maxn];
struct Node{
long long l, r, maxx, lazy_add, lazy_erase;
bool flag_add, flag_erase;
}tr[8 * maxn];
void pushup(int k){
tr[k].maxx = max(tr[k << 1].maxx, tr[k << 1 | 1].maxx);
}
void pushdown(int k){
int lc = k << 1, rc = k << 1 | 1;
if(tr[k].flag_erase){
tr[rc].maxx = tr[lc].maxx = tr[lc].lazy_erase = tr[rc].lazy_erase = tr[k].lazy_erase;
tr[lc].flag_erase = tr[rc].flag_erase = tr[k].flag_erase;
tr[k].lazy_erase = 0;
tr[k].flag_erase = false;
}
if(tr[k].flag_add){
tr[lc].maxx = tr[lc].maxx + tr[k].lazy_add;
tr[lc].lazy_add += tr[k].lazy_add;
tr[rc].maxx = tr[rc].maxx + tr[k].lazy_add;
tr[rc].lazy_add += tr[k].lazy_add;
tr[lc].flag_add = tr[rc].flag_add = tr[k].flag_add;
tr[k].lazy_add = 0;
tr[k].flag_add = false;
}
}
void lazy_add(int k, int v){
if(tr[k].flag_erase){
tr[k].lazy_erase += v;
tr[k].maxx += v;
}
else{
tr[k].flag_add = true;
tr[k].lazy_add += v;
tr[k].maxx += v;
}
}
void lazy_erase(int k, int v){
tr[k].flag_erase = true;
tr[k].lazy_add = 0;
tr[k].lazy_erase = v;
tr[k].maxx = v;
}
void build(int k, int l, int r){
tr[k].l = l;
tr[k].r = r;
tr[k].lazy_add = tr[k].lazy_erase = tr[k].maxx = 0;
tr[k].flag_add = tr[k].flag_erase = false;
if(l == r){
tr[k].maxx = a[l];
return;
}
int mid = (l + r) >> 1;
int lc = k << 1, rc = k << 1 | 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(k);
}
void update_add(int k, int l, int r, int v){
if(tr[k].l >= l && tr[k].r <= r){
// pushup(k);
lazy_add(k, v);
return;
}
if(tr[k].flag_add || tr[k].flag_erase) pushdown(k);
int mid = (tr[k].l + tr[k].r) >> 1;
int lc = k << 1, rc = k << 1 | 1;
if(r <= mid) update_add(lc, l, r, v);
else if(l > mid) update_add(rc, l, r, v);
else{
update_add(lc, l, mid, v);
update_add(rc, mid + 1, r, v);
}
pushup(k);
}
void update_erase(int k, int l, int r, int v){
if(tr[k].l >= l && tr[k].r <= r){
// pushup(k);
lazy_erase(k, v);
return;
}
if(tr[k].flag_add || tr[k].flag_erase) pushdown(k);
int mid = (tr[k].l + tr[k].r) >> 1;
int lc = k << 1, rc = k << 1 | 1;
if(r <= mid) update_erase(lc, l, r, v);
else if(l > mid) update_erase(rc, l, r, v);
else{
update_erase(lc, l, mid, v);
update_erase(rc, mid + 1, r, v);
}
pushup(k);
}
long long query(int k, int l, int r){
if(tr[k].l >= l && tr[k].r <= r){
return tr[k].maxx;
}
if(tr[k].flag_add || tr[k].flag_erase) pushdown(k);
int mid = (tr[k].l + tr[k].r) >> 1;
int lc = k << 1, rc = k << 1 | 1;
long long ans = -INF;
if(r <= mid) ans = query(lc, l, r);
else if(l > mid) ans = query(rc, l, r);
else ans = max(query(lc, l, mid), query(rc, mid + 1, r));
pushup(k);
return ans;
}
void print(int k){
if(tr[k].l){
print(k << 1);
cout << k << " l:"<< tr[k].l << " r:" << tr[k].r << " maxx:" << tr[k].maxx
<< " lazy_add:" << tr[k].lazy_add << " lazy_erase:" << tr[k].lazy_erase << endl;
print(k << 1 | 1);
}
}
#define int int
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while(q --){
cin >> op >> l >> r;
if(op == 1){
cin >> x;
update_erase(1, l, r, x);
// print(1);
}
else if(op == 2){
cin >> x;
update_add(1, l, r, x);
// print(1);
}
else{
cout << query(1, l, r) << endl;
// print(1);
}
}
return 0;
}
by Februrary @ 2024-03-16 15:11:41
我也是过不了这几个点,我看了你的push_down()部分的代码,我觉得两个标签下放时应该是有顺序的,你好像没有考虑。比如对于下面这数据
5 3
1 1 1 1 1
1 1 5 2
2 1 5 3
3 1 3
结果应该为5
如果调换两行
5 3
1 1 1 1 1
2 1 5 3
1 1 5 2
3 1 3
结果应该为2
如果没有考虑顺序结果应该是一样的,你可以试试,但是我后面考虑了顺序提交一样过不了
by Februrary @ 2024-03-16 15:12:19
@Peter_0327 可以看一下上面的回复
by Peter_0327 @ 2024-03-17 14:28:54
@Februrary 谢谢,我再看看