线段树50pts求助

rt.

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 10,INF = 0x3f3f3f3f;

struct node {
    int l,r;
    int val,mul;
    int add;
} tr[N << 2];

int n,m;
int a[N];

inline void pushup(int u) { tr[u].val = max(tr[u << 1].val,tr[u << 1 | 1].val); }

inline void pushdown(int u) {
    if (tr[u].mul != INF) {
        tr[u << 1].val = tr[u].mul;
        tr[u << 1].mul = tr[u].mul;
        tr[u << 1].add = 0;
        tr[u << 1 | 1].val = tr[u].mul;
        tr[u << 1 | 1].mul = tr[u].mul;
        tr[u << 1 | 1].add = 0;
        tr[u].mul = INF;
    }
    tr[u << 1].val += tr[u].add;
    tr[u << 1].add += tr[u].add;
    tr[u << 1 | 1].val += tr[u].add;
    tr[u << 1 | 1].add += tr[u].add;
    tr[u].add = 0;
}

inline void build(int u,int l,int r) {
    tr[u] = {l,r,0,INF,0};
    if (l == r) {
        tr[u].val = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
    pushup(u);
}

inline void modify1(int u,int l,int r,int k) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].val = k;
        tr[u].mul = k;
        tr[u].add = 0;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify1(u << 1,l,r,k);
    if (mid < r) modify1(u << 1 | 1,l,r,k);
    pushup(u);
}

inline void modify2(int u,int l,int r,int k) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].val += k;
        tr[u].add += k;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify2(u << 1,l,r,k);
    if (mid < r) modify2(u << 1 | 1,l,r,k);
    pushup(u);
}

inline int query(int u,int l,int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
    pushdown(u);
    int res = -INF;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res = query(u << 1,l,r);
    if (mid < r) res = max(res,query(u << 1 | 1,l,r));
    return res;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    build(1,1,n);
    while (m -- ) {
        int op,l,r;
        cin >> op >> l >> r;
        if (op == 1) {
            int k;
            cin >> k;
            modify1(1,l,r,k);
        } else if (op == 2) {
            int k;
            cin >> k;
            modify2(1,l,r,k);
        } else cout << query(1,l,r) << endl;
    }
    return 0;
}

WA 4个点，TLE 一个点