线段树20分求调

#include <bits/stdc++.h>
using namespace std;

const int MAXLENGTH = 1000005;

int N, M;
int a[MAXLENGTH] = {0}; // 记录每个元素的值
long long d[4 * MAXLENGTH] = {0}; // 记录每个结点代表区间的最大值
long long b[4 * MAXLENGTH] = {0}; // 记录加法懒标记
long long e[4 * MAXLENGTH] = {0}; // 记录赋值懒标记
bool flag[4 * MAXLENGTH] = {0}; // 是否需要赋值

void build(int s, int t, int p){
    // 对 [s,t] 区间建立线段树,当前根的编号为 p
    if(s==t){
        d[p] = a[s];
        return;
    }
    int m = s + ((t - s) >> 1);
    build(s, m, 2 * p);
    build(m+1, t, 2*p+1);
    d[p] = (d[2*p] + d[2*p+1]);
}
void pushdown(int s, int t, int p){
    // 表示[s, t] 区间的节点, p为该节点的编号
    int m = s + ((t - s) >> 1);
    if(flag[p] && s != t){
        // 更新子节点的值
        d[2*p] = e[p] + b[p];
        d[2*p+1] = e[p] + b[p];
        // 下传懒标记
        e[2*p] = e[p];
        e[2*p+1] = e[p];
        b[2*p] = b[p];
        b[2*p+1] = b[p];
        flag[2*p] = 1;
        flag[2*p+1] = 1;
        // 重置当前节点的懒标记
        flag[p] = 0;
        b[p] = 0;
        return;
    }
    if(b[p] && s != t){
        // 更新子节点的值
        d[2*p] += b[p];
        d[2*p+1] += b[p];
        // 下传懒标记
        b[2*p] += b[p];
        b[2*p+1] += b[p];
        // 重置当前节点的懒标记
        b[p] = 0;
    }
}
void pushup(int p){
    // 表示[s, t] 区间的节点, p为该节点的编号
    d[p] = max(d[2*p], d[2*p+1]);
}
void update_add(int l, int r, int c, int s, int t, int p){
    // [l, r] 为修改区间, c 为被修改的元素的变化量, 
    // [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if(l <= s && r >= t){ // [s, t]是[l, r]的子区间
        d[p] += c;
        b[p] += c;
        return;
    }
    pushdown(s, t, p);
    int m = s + ((t - s) >> 1);
    if(l <= m) // 需要更新左子节点
        update_add(l, r, c, s, m, 2*p);
    if(r > m) // 需要更新右子节点
        update_add(l, r, c, m+1, t, 2*p+1);
    pushup(p);
}
void update_rename(int l, int r, int c, int s, int t, int p){
    // [l, r] 为修改区间, c 为被修改的元素的变化量, 
    // [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if(l <= s && r >= t){ // [s, t]是[l, r]的子区间
        d[p] = c;
        b[p] = 0;
        e[p] = c;
        flag[p] = 1;
        return;
    }
    pushdown(s, t, p);
    int m = s + ((t - s) >> 1);
    if(l <= m) // 需要更新左子节点
        update_rename(l, r, c, s, m, 2*p);
    if(r > m) // 需要更新右子节点
        update_rename(l, r, c, m+1, t, 2*p+1);
    pushup(p);
}
long long solve(int l, int r, int s, int t, int p){
    // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
    if(l <= s && r >= t) // [s, t]是[l, r]的子区间
        return d[p];
    int m = s + ((t - s) >> 1);
    pushdown(s, t, p);
    long long maxi = 1<<31;
    if(l <= m) maxi = max(maxi, solve(l, r, s, m, 2*p));
    if(r > m) maxi = max(maxi, solve(l, r, m+1, t, 2*p+1));
    return maxi;
}

int main(){  
    cin>>N>>M;
    for(int i = 1; i <= N; i++){
        cin>>a[i];
    }
    build(1, N, 1);

    int op;
    int x, y, k;
    for(int i = 1; i <= M; i++){
        cin>>op>>x>>y;
        if(op == 1){
            // 将区间[x, y]内每个数赋为k
            cin>>k;
            update_rename(x, y, k, 1, N, 1);
        }
        else if(op == 2){
            // 将区间[x, y]内每个数加上k
            cin>>k;
            update_add(x, y, k, 1, N, 1);
        }
        else if(op==3){
            // 输出区间[x, y]内的最大值
            cout<<solve(x, y, 1, N, 1)<<endl;
        }
    }
    return 0;
}