【赏4关】线段树板题60pts求调

rt,WA#7~10。

好像有一堆60pts?

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, opt, x, y, k, a[1000005];
struct segment{
    ll l, r, maxn, lazy, lazy2;
    bool flag;
}b[5000000];
void pushdown(ll t){
    b[t * 2].maxn += b[t].lazy2;
    b[t * 2 + 1].maxn += b[t].lazy2;
    b[t * 2].lazy2 += b[t].lazy2;
    b[t * 2 + 1].lazy2 += b[t].lazy2;
    b[t].lazy2 = 0;
    if(b[t].flag){
        b[t * 2].maxn = b[t].lazy;
        b[t * 2 + 1].maxn = b[t].lazy;
        b[t * 2].lazy = b[t].lazy;
        b[t * 2 + 1].lazy = b[t].lazy;
        b[t * 2].flag = true;
        b[t * 2 + 1].flag = true;
        b[t * 2].lazy2 = 0;
        b[t * 2 + 1].lazy2 = 0;
        b[t].lazy = 0;
        b[t].flag = false;
    }
} 
void build(ll s, ll e, ll t){
    b[t].l = s;
    b[t].r = e;
    b[t].flag = false;
    if(s == e){
        b[t].maxn = a[s];
        return;
    }
    ll p = s + ((e - s) >> 1);
    build(s, p, t * 2);
    build(p + 1, e, t * 2 + 1);
    b[t].maxn = max(b[t * 2].maxn, b[t * 2 + 1].maxn);
    return;
}
ll scarch(ll t){
    if(x <= b[t].l && y >= b[t].r){
        return b[t].maxn;
    }
    ll p = b[t].l + ((b[t].r - b[t].l) >> 1);
    pushdown(t);
    ll ans = LLONG_MIN;
    if(x <= p){
        ans = max(ans, scarch(t * 2));
    }
    if(y > p){
        ans = max(ans, scarch(t * 2 + 1));
    }
    return ans;
}
void update1(ll t){
    if(x <= b[t].l && y >= b[t].r){
        b[t].maxn = k;
        b[t].lazy = k;
        b[t].lazy2 = 0;
        b[t].flag = true;
        return;
    }
    ll p = b[t].l + ((b[t].r - b[t].l) >> 1);
    pushdown(t);
    if(x <= p){
        update1(t * 2);
    }
    if(y > p){
        update1(t * 2 + 1);
    }
    b[t].maxn = max(b[t * 2].maxn, b[t * 2 + 1].maxn);
    return;
}
void update2(ll t){
    if(x <= b[t].l && y >= b[t].r){
        b[t].maxn += k;
        if(b[t].flag){
            b[t].lazy += k;
        }
        else{
            b[t].lazy2 += k;
        }
        return;
    }
    b[t].flag = false;
    ll p = b[t].l + ((b[t].r - b[t].l) >> 1);
    pushdown(t);
    if(x <= p){
        update2(t * 2);
    }
    if(y > p){
        update2(t * 2 + 1);
    }
    b[t].maxn = max(b[t * 2].maxn, b[t * 2 + 1].maxn);
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    build(1, n, 1);
    for(int i = 0; i < m; i++){
        cin >> opt;
        if(opt == 1){
            cin >> x >> y >> k;
            update1(1);
        }
        else if(opt == 3){
            cin >> x >> y;
            cout << scarch(1) << endl;
        }
        else{
            cin >> x >> y >> k;
            update2(1);
        }
    }
    return 0;
}