mxqz，刚学线段树，TLE 40pts

RT,调了半天还是TLE

#include <cstdio>

#define LL long long
#define MAXN 1000010 // Datas MAX
#define INF 0x3f3f3f3f3f3f3f3f
#define Null -1145141919810
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define make_mid(l, r) int mid = ((l) + (r)) / 2
#define ffor(_INDEX,l,r) for (int _INDEX = (l); _INDEX <= (r); _INDEX++)

template <typename T> inline void read (T &x);
template <typename T, typename ... Args> inline void read (T &t, Args&... args);

struct segment_tree {
    LL sum_tag, cover_tag, mx;
    int l, r;
};

int n, q;
LL arr[MAXN];
segment_tree tree[MAXN << 2];

LL query (int, int, int);
void update1 (int, int, int, LL);
void update2 (int, int, int, LL);
void pushdown (int);
void build_tree (int, int, int);

signed main (void) {

    read (n, q);
    ffor (i, 1, n) read (arr[i]);

    build_tree (1, 1, n);

    while (q--) {
        LL d;
        int op, l, r;
        read (op);
        if (op == 3) {
            read (l, r);
            printf ("%lld\n", query (1, l, r));
        } else if (op == 1) {
            read (l, r, d);
            update1 (1, l, r, d);
        } else {
            read (l, r, d);
            update2 (1, l, r, d);
        }
    }

    return 0;
}

void pushup (int root) {
    tree[root].mx = max (tree[lson (root)].mx, tree[rson (root)].mx);
}

void build_tree (int root, int l, int r) {
    tree[root].l = l, tree[root].r = r, tree[root].cover_tag = Null, tree[root].mx = -INF;
    if (l == r) {
        tree[root].mx = arr[l];
        return ; 
    }

    make_mid (tree[root].l, tree[root].r);
    if (mid >= l) build_tree (lson (root), l, mid);
    if (mid < r) build_tree (rson (root), mid + 1, r);
    pushup (root);
}

void update1 (int root, int l, int r, LL d) {
    if (tree[root].l >= l && tree[root].r <= r) {
        tree[root].sum_tag = 0;
        tree[root].cover_tag = d;
        tree[root].mx = d;
        return ;
    }

    pushdown (root);
    make_mid (tree[root].l, tree[root].r);
    if (mid >= l) update1 (lson (root), l, r, d);
    if (mid < r) update1 (rson (root), l, r, d);
    pushup (root);
}

void update2 (int root, int l, int r, LL d) {    
    if (tree[root].l >= l && tree[root].r <= r) {
        tree[root].sum_tag += d;
        tree[root].mx += d;
        return ;
    }

    pushdown (root);
    make_mid (tree[root].l, tree[root].r);
    if (mid >= l) update2 (lson (root), l, r, d);
    if (mid < r) update2 (rson (root), l, r, d);
    pushup (root);
}

void pushdown (int root) {
    if (tree[root].cover_tag != Null) {
        tree[root].sum_tag = 0;
        tree[lson (root)].sum_tag = tree[rson (root)].sum_tag = 0;
        tree[lson (root)].mx = tree[rson (root)].mx = tree[root].cover_tag;
        tree[lson (root)].cover_tag = tree[rson (root)].cover_tag = tree[root].cover_tag;
        tree[root].cover_tag = Null;
    } else {
        if (tree[root].sum_tag) {
            tree[lson (root)].sum_tag += tree[root].sum_tag;
            tree[rson (root)].sum_tag += tree[root].sum_tag;
            tree[lson (root)].mx += tree[root].sum_tag;
            tree[rson (root)].mx += tree[root].sum_tag;
            tree[root].sum_tag = 0;
        }
    }
}

LL query (int root, int l, int r) {
    if (tree[root].l >= l && tree[root].r <= r) {
        return tree[root].mx;
    }

    pushdown (root);
    LL ans = -INF;
    make_mid (tree[root].l, tree[root].r);
    if (mid >= l) ans = max (ans, query (lson (root), l, r));
    if (mid < r) ans = max (ans, query (rson (root), l, r));

    return ans;
}

template <typename T> inline void read (T &x) {
    T f = 1; x = 0;
    char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-') { f = -1; };
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar ();
    }
    x *= f;
}

template <typename T, typename ... Args> inline void read (T &t, Args&... args) {
    read(t), read(args...);
}