萌新求调线段树裸题

AC at 1，3. other WA.在线等

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL Inf = 1e15;
const int maxn = 1e6 + 10;
LL tr[maxn << 1], lazy1[maxn << 1], lazy2[maxn << 1];
int lson[maxn << 1], rson[maxn << 1], tot;
int a[maxn];
void pushup(int k){
    tr[k] = max(tr[lson[k]], tr[rson[k]]);
}
void pushdown1(int l, int r, int k){
    if(lazy1[k]){
        int mid = (l + r) >> 1;
        tr[lson[k]] += (mid - l + 1) * lazy1[k];
        tr[rson[k]] += (r - mid) * lazy1[k];
        lazy1[lson[k]] += lazy1[k];
        lazy1[rson[k]] += lazy1[k];
        lazy1[k] = 0;
    }
}
void pushdown2(int k){
    if(lazy2[k] != Inf){
        tr[lson[k]] = lazy2[k];
        tr[rson[k]] = lazy2[k];
        lazy2[lson[k]] = lazy2[k];
        lazy2[rson[k]] = lazy2[k];
        lazy1[k] = 0;
        lazy1[lson[k]] = 0;
        lazy1[rson[k]] = 0;
        lazy2[k] = Inf;
    }
} 
void build(int l, int r, int &k){
    k = ++tot;
    lazy2[k] = Inf;
    if(l == r){
        tr[k] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l , mid, lson[k]);
    build(mid + 1, r, rson[k]);
    pushup(k);
}
void update1(int l, int r, int L, int R, int k, LL x){
    if(l >= L && r <= R){
        tr[k] += (r - l + 1) * x;
        lazy1[k] += x;
        return;
    }
    pushdown2(k);
    pushdown1(l, r, k);
    int mid = (l + r) >> 1;
    if(L <= mid) update1(l, mid, L, R, lson[k], x);
    if(R > mid) update1(mid + 1, r, L, R, rson[k], x);
    pushup(k);
}
void update2(int l, int r, int L, int R, int k, LL x){
    if(l >= L && r <= R){
        tr[k] =  x;
        lazy2[k] = x;
        lazy1[k] = 0;
        return;
    }
    pushdown2(k);
    pushdown1(l, r, k);
    int mid = (l + r) >> 1;
    if(L <= mid) update2(l, mid, L, R, lson[k], x);
    if(R > mid) update2(mid + 1, r, L, R, rson[k], x);
    pushup(k);
}

LL getsum(int l, int r, int L, int R, int k){
    if(l >= L && r <= R){
        return tr[k];
    }
    pushdown2(k);
    pushdown1(l, r, k);
    int mid = (l + r) >> 1;
    LL sum = -Inf;
    if(L <= mid) sum = max(sum, getsum(l, mid, L, R, lson[k]));
    if(R > mid) sum = max(sum, getsum(mid + 1, r, L, R, rson[k]));
    return sum;
}
int n, q;
int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int tmp = 0;    
    build(1, n, tmp);
    while(q--){
        int op;
        scanf("%d", &op);
        if(op == 1){
            int L, R; LL x;
            scanf("%d%d%lld", &L, &R, &x);
            update2(1, n, L, R, 1, x);          
        }
        else if(op == 2){
            int L, R; LL x;
            scanf("%d%d%lld", &L, &R, &x);
            update1(1, n, L, R, 1, x);
        }
        else{
            int L, R;
            scanf("%d%d", &L, &R);
            printf("%lld\n", getsum(1, n, L, R, 1));
        }
    }   
}