60pts求助,悬棺

P1253 扶苏的问题

SegmentTree_ @ 2023-11-03 16:02:01

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lid (id << 1)
#define rid (id << 1 | 1)
#define none -2147483647
struct node{
    int l, r;
    ll maxx, lazy, lazy2;
}tr[4000005];
int n, m, op, l, r, k, a[1000005];
void pushup(int id){
    tr[id].maxx = max(tr[lid].maxx, tr[rid].maxx);
}
void pushdown(int id){
    if (tr[id].l == tr[id].r) return;
    if (tr[id].lazy2 != none){
        tr[lid].lazy2 = tr[id].lazy2;
        tr[rid].lazy2 = tr[id].lazy2;
        tr[lid].maxx = tr[id].lazy2;
        tr[rid].maxx = tr[id].lazy2;
        tr[id].lazy2 = none;
    }
    else if (tr[id].lazy){
        tr[lid].lazy += tr[id].lazy;
        tr[rid].lazy += tr[id].lazy;
        tr[lid].maxx += tr[id].lazy;
        tr[rid].maxx += tr[id].lazy;
        tr[id].lazy = 0;
    }
}
void build(int id, int l, int r){
    tr[id].l = l;
    tr[id].r = r;
    tr[id].lazy = 0;
    tr[id].lazy2 = none;
    if (l == r){
        tr[id].maxx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    pushup(id);
}
void add(int id, int l, int r, int x){
    pushdown(id);
    if (l <= tr[id].l && tr[id].r <= r){
        tr[id].maxx += x;
        if (tr[id].lazy2 != none) tr[id].lazy2 += x;
        else tr[id].lazy += x;
        return;
    }
    int mid = (tr[id].l + tr[id].r) / 2;
    if (r <= mid) add(lid, l, r, x);
    else if (l > mid) add(rid, l, r, x);
    else add(lid, l, mid, x), add(rid, mid + 1, r, x);
    pushup(id);
}
void modify(int id, int l, int r, int x){
    pushdown(id);
    if (l <= tr[id].l && tr[id].r <= r){
        tr[id].maxx = x;
        tr[id].lazy2 = x;
        tr[id].lazy = 0;
        return;
    }
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (r <= mid) modify(lid, l, r, x);
    else if (l > mid) modify(rid, l, r, x);
    else modify(lid, l, mid, x), modify(rid, mid + 1, r, x);
    pushup(id);
}
ll query(int id, int l, int r){
    pushdown(id);
    if (l <= tr[id].l && tr[id].r <= r) return tr[id].maxx;
    int mid = (tr[id].l + tr[id].r) / 2;
    if (r <= mid) return query(lid, l, r);
    if (l > mid) return query(rid, l, r);
    return max(query(lid, l, mid), query(rid, mid + 1, r));
}
void print_seg(){
    for (int i = 1;i <= n;i++) cout << query(1, i, i) << ' ';
    cout << '\n';
}
int main(){
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    build(1, 1, n);
    //print_seg();
    while(m--){
        cin >> op >> l >> r;
        if (op == 1){
            cin >> k;
            modify(1, l, r, k);
        }
        else if (op == 2){
            cin >> k;
            add(1, l, r, k);
        }
        else{
            cout << query(1, l, r) << '\n';
        }
        //print_seg();
    }
    return 0;
}

by ademik @ 2023-11-03 17:09:52

@tianyu_awa

push_down

if (tr[id].lazy2 != none){
    加入
    tr[lid].lazy = tr[rid].lazy = 0;
}
// 这里删除 else, 虽然我也不知道为什么。。。
if (tr[id].lazy){

}

by ademik @ 2023-11-03 17:10:48

然后你可能还需要亿点点卡常, 比如加个快读什么的。


by SegmentTree_ @ 2023-11-03 17:16:31

@ademik 好的,谢谢


|