40pts求助

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

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
int maxv[N * 4], sumv[N * 4], a[N], lazy[4 * N];
int n, m;

void pushup(int id) {
    maxv[id] = max(maxv[id << 1], maxv[id << 1 | 1]);
    sumv[id] = sumv[id << 1] + sumv[id << 1 | 1];
}

void pushdown(int id, int l, int r) {
    if (lazy[id]) {
        int mid = (l + r) >> 1;
        //标记的下标
        lazy[id << 1] += lazy[id];
        lazy[id << 1 | 1] += lazy[id];
        //左区间更新
        maxv[id << 1] += lazy[id];
        sumv[id << 1] += (mid - l + 1) * lazy[id];
        //右区间更新
        maxv[id << 1 | 1] += lazy[id];
        sumv[id << 1 | 1] += (r - mid) * lazy[id];  
        lazy[id] = 0;            
    }
}

//id 表示节点编号，l r 表示这个节点对应的区间 
void build(int id, int l, int r) {
    if (l == r) {
        //如果当前区间是长度为 1 的叶子节点 
        maxv[id] = sumv[id] = a[l];
        return;
    }
    //否则的话从中间拆分开左右两个区间 
    int mid = (l + r) >> 1;//(l + r) >> 1 ==> (l + r) / 2 
    build(id << 1, l, mid);//id << 1 ==> id * 2 
    build(id << 1 | 1, mid + 1, r);//id << 1 | 1 ==> id * 2 + 1 
    //左右两个孩子的结果全部计算完毕后
    //把结果合并到当前节点 
    pushup(id);
} 

void interval_update(int id, int l, int r, int x, int y, int v) {//区间更新
    if (x <= l && r <= y) {
        lazy[id] = v;
        maxv[id] = v;
        return;
    }
    pushdown(id, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) {
        interval_update(id << 1, l, mid, x, y, v);
    } 
    if (y > mid) {
        interval_update(id << 1 | 1, mid + 1, r, x, y, v);
    }
    pushup(id);
}

int query_max(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return maxv[id];
    }
    pushdown(id, l, r);
    int mid = (l + r) >> 1;
    int ans = -INF;
    if (x <= mid) {
        ans = max(ans, query_max(id << 1, l, mid, x, y));
    }  
    if (y > mid) {
        ans = max(ans, query_max(id << 1 | 1, mid + 1, r, x, y));
    }
    return ans;
}

void add(int id, int l, int r, int x, int y, int v) {
    if (x <= l && y >= r) {
        maxv[id] += v;
        lazy[id] += v;
        return;
    }
    pushdown(id, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) {
        add(id << 1, l, mid, x, y, v);
    }  
    if (y > mid) {
        add(id << 1 | 1, mid + 1, r, x, y, v);
    }
    maxv[id] = max(maxv[id << 1], maxv[id << 1 | 1]);
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    while (q--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            interval_update(1, 1, n, l, r, x);
        } else if (op == 2) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            add(1, 1, n, l, r, x);          
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query_max(1, 1, n, l, r));
        }
    }
    return 0;
}

提交记录