RT, AC #5 #6。 20 PTS。

代码最下面贴了Data #1

#include <bits/stdc++.h> 
#define IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr) 
#define rep(i, a, b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for (int i = a; i >= b; i--)
#define lc(x) x << 1ll 
#define rc(x) x << 1ll | 1ll
#define lowbit(x) ((x) & (-x))
#define LEN_LC (tree[lc(i)].r - tree[lc(i)].l + 1) 
#define LEN_RC (tree[rc(i)].r - tree[rc(i)].l + 1) 
#define LEN (tree[i].r - tree[i].l + 1)  
#define int long long
const int N = 5e5 + 7; 
const int inf = INT_MAX;  
int n, m; 
int a[N], b[N]; 
struct Tree {
	int l, r; 
	int maxa, maxb, sum; 
	int cnt, semax; 
	int lazy1; 
	int lazy2; 
	int lazy3; 
	int lazy4; 
}tree[N << 2]; 

void push_up(int i) { 
	tree[i].sum = tree[lc(i)].sum + tree[rc(i)].sum;  
	tree[i].maxa = std::max(tree[lc(i)].maxa, tree[rc(i)].maxa); 
	tree[i].maxb = std::max(tree[lc(i)].maxb, tree[rc(i)].maxb);
	if(tree[lc(i)].maxa == tree[rc(i)].maxa) {
		tree[i].semax = std::max(tree[lc(i)].semax, tree[rc(i)].semax);
		tree[i].cnt = tree[lc(i)].cnt + tree[rc(i)].cnt; 
	}
	else if(tree[lc(i)].maxa > tree[rc(i)].maxa) {
		tree[i].semax = std::max(tree[lc(i)].semax, tree[rc(i)].maxa);
		tree[i].cnt = tree[lc(i)].cnt;  
	}
	else {	
		tree[i].semax = std::max(tree[lc(i)].maxa, tree[rc(i)].semax); 
		tree[i].cnt = tree[rc(i)].cnt; 
	}
}

void add_tag(int i, int s1, int s2, int s3, int s4) {
    tree[i].sum += s1 * tree[i].cnt + s2 * (tree[i].r - tree[i].l + 1 - tree[i].cnt); 
	tree[i].maxb = std::max(tree[i].maxb, tree[i].maxa + s3); 
	tree[i].maxa += s1; 	
	if(tree[i].semax != -inf) tree[i].semax += s2; 
	tree[i].lazy3 = std::max(tree[i].lazy3, tree[i].lazy1 + s3); 
	tree[i].lazy4 = std::max(tree[i].lazy4, tree[i].lazy2 + s4); 
	tree[i].lazy1 += s1, tree[i].lazy2 += s2;  
}

void push_down(int i) {

	int MAX = std::max(tree[lc(i)].maxa, tree[rc(i)].maxa);  
	if(tree[lc(i)].maxa == MAX) {
		add_tag(lc(i), tree[i].lazy1, tree[i].lazy2, tree[i].lazy3, tree[i].lazy4); 
	} else {
		add_tag(lc(i), tree[i].lazy2, tree[i].lazy2, tree[i].lazy4, tree[i].lazy4); 
	}

	if(tree[rc(i)].maxa == MAX) {
		add_tag(rc(i), tree[i].lazy1, tree[i].lazy2, tree[i].lazy3, tree[i].lazy4); 
	} else {
		add_tag(rc(i), tree[i].lazy2, tree[i].lazy2, tree[i].lazy4, tree[i].lazy4); 
	}

	tree[i].lazy1 = tree[i].lazy2 = tree[i].lazy3 = tree[i].lazy4 = 0; 
}

void build(int i, int L, int R) {
	tree[i].l = L, tree[i].r = R;
	if(L == R) {
		tree[i].sum = tree[i].maxa = tree[i].maxb = a[L]; 
		tree[i].cnt = 1; 
		tree[i].semax = -inf; 
		return ;  
	}
	int mid = (L + R) >> 1; 
	build(lc(i), L, mid); 
	build(rc(i), mid + 1, R); 
	push_up(i); 
}

void modify1(int i, int L, int R, int k) {
	if(L <= tree[i].l && tree[i].r <= R) {
		add_tag(i, k, k, k, k); 
		return ; 
	}
	push_down(i); 
	if(tree[lc(i)].r >= L) modify1(lc(i), L, R, k); 
	if(tree[rc(i)].l <= R) modify1(rc(i), L, R, k); 
	push_up(i); 
}

void modify2(int i, int L, int R, int k) {
    if(tree[i].l > R || tree[i].r < L || k >= tree[i].maxa) return; 
	if(L <= tree[i].l && tree[i].r <= R && k > tree[i].semax) {
        add_tag(i, k - tree[i].maxa, k - tree[i].maxa, 0, 0); 
		return ; 
	}
	push_down(i); 
	if(tree[lc(i)].r >= L) modify2(lc(i), L, R, k); 
	if(tree[rc(i)].l <= R) modify2(rc(i), L, R, k); 
	push_up(i); 
}

int query1(int i, int L, int R) {
	if(L <= tree[i].l && tree[i].r <= R) {
		return tree[i].sum; 
	}
	push_down(i); 
    int res = 0; 
    if(tree[lc(i)].r >= L) res += query1(lc(i), L, R); 
    if(tree[rc(i)].l <= R) res += query1(rc(i), L, R);  
	return res; 
}

int query2(int i, int L, int R) { 
	if(tree[i].l > R || tree[i].r < L)  return -inf; 
	if(L <= tree[i].l && tree[i].r <= R) {
		return tree[i].maxa; 
	}
	push_down(i); 
    int max = -inf; 
	if(tree[lc(i)].r >= L) max = std::max(max, query2(lc(i), L, R)); 
    if(tree[rc(i)].l <= R) max = std::max(max, query2(rc(i), L, R));  
	return max; 
}

int query3(int i, int L, int R) { 
	if(tree[i].l > R || tree[i].r < L)   return -inf; 
	if(L <= tree[i].l && tree[i].r <= R) {
		return tree[i].maxb; 
	}
	push_down(i); 
	int max = -inf; 
	if(tree[lc(i)].r >= L) max = std::max(max, query3(lc(i), L, R)); 
    if(tree[rc(i)].l <= R) max = std::max(max, query3(rc(i), L, R));  
	return max; 
}

void print_seg(){
    rep(i, 1, n) {
        std::cout << query1(1, i, i) << " " ;
    }
    std::cout << std::endl; 
}

void solve() {
	std::cin >> n >> m; 
	rep(i, 1, n) {
		std::cin >> a[i]; 
	}
	build(1, 1, n); 
	while(m--) {
		int opt; 
		std::cin >> opt;
		if(opt == 1) {
			int l, r, k; 
			std::cin >> l >> r >> k; 
			modify1(1, l, r, k); 
		}

		if(opt == 2) {
			int l, r, k; 
			std::cin >> l >> r >> k; 
			modify2(1, l, r, k); 
		}

		if(opt == 3) {
            int l, r;
            std::cin >> l >> r; 
			std::cout << query1(1, l, r) << std::endl; 
		}

		if(opt == 4) {
            int l, r;
            std::cin >> l >> r;  
			std::cout << query2(1, l, r) << std::endl; 
		}

		if(opt == 5) {
            int l, r; 
            std::cin >> l >> r; 
			std::cout << query3(1, l, r) << std::endl; 
		}
       // std::cout << "now options is:" << opt << " seg:"; print_seg(); 
	}
}
 
signed main() {
    IOS; 
    solve(); 
    return 0; 
}

/*

Big Data:

Input:
20 50
-36 42 42 11 -3 -5 -36 9 -17 22 -35 -46 -35 15 28 -5 25 48 -42 -14
5 9 14
1 3 15 -26
4 2 5
1 13 14 8
5 1 19
4 3 11
5 4 16
3 1 20
3 10 20
5 7 18
1 13 15 33
4 6 14
5 7 16
3 2 6
1 3 5 -9
4 14 18
5 1 11
1 3 3 -25
5 5 14
3 6 12
3 5 19
5 2 10
2 2 18 -36
5 14 15
1 7 17 -26
3 10 10
1 5 18 41
4 2 9
5 15 20
1 19 19 37
3 6 13
5 9 11
1 6 15 23
1 1 11 41
2 10 10 -7
5 3 15
5 3 16
1 4 14 46
3 18 20
5 11 16
4 10 19
1 12 12 12
5 6 9
2 2 20 -36
1 6 10 42
2 13 13 9
5 2 8
5 7 15
1 18 19 -42
5 2 13

Ans Output:

22
42
48
16
28
-354
-179
48
30
35
-17
48
42
30
-290
-257
42
35
-62
5
48
-236
22
69
69
-14
64
64
115
115
89
115

Bad Output #1:

22
42
48
16
28
-354
-179
48
30
35
-17
48
42
30
-290
-257
42
35
-62
5
48
-305 <- Bad
22
69
69
-14
48 <- Bad
48 <- Bad
115
115
89
115


 */