求条玄关

#include <bits/stdc++.h>

#define int long long
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

using namespace std;

const int N = 5e5 + 5;

int n, m, a[N];

struct mat {
	int a[2][2];
	mat() {
	    memset(a, -0x3f, sizeof(a));	
	}
	mat operator * (const mat b) const {
		mat c;
		for (int i = 0; i < 2; ++ i )
		    for (int j = 0; j < 2; ++ j )
		        for (int k = 0; k < 2; ++ k )
		            c.a[i][j] = max(c.a[i][j], a[i][k] + b.a[k][j]);
		
		return c;
	}
	mat operator + (const mat b) const {
		mat c;
		for (int i = 0; i < 2; ++ i )
		    for (int j = 0; j < 2; ++ j )
		        c.a[i][j] = max(a[i][j], b.a[i][j]);
		        
		return c;
	} 
};

struct node {
	int l, r, m1, m2, cnt, sum, add1, add2;
	mat a, add, tag;
	int f1, f2;
};

node t[4 * N];

void push_up (int p) {
	t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
	t[p].m1 = max(t[ls(p)].m1, t[rs(p)].m1);
	t[p].m2 = max(t[ls(p)].m2, t[rs(p)].m2);
	if (t[p].m1 != t[ls(p)].m1) t[p].m2 = max(t[p].m2, t[ls(p)].m1);
	if (t[p].m1 != t[rs(p)].m1) t[p].m2 = max(t[p].m2, t[rs(p)].m1);
	t[p].cnt = 0;
	if (t[p].m1 == t[ls(p)].m1) t[p].cnt += t[ls(p)].cnt;
	if (t[p].m1 == t[rs(p)].m1) t[p].cnt += t[rs(p)].cnt;
	t[p].a = t[ls(p)].a + t[rs(p)].a;
	return;
}

void build (int l, int r, int p) {
	t[p].l = l, t[p].r = r;
	if (l == r) {
		t[p].sum = t[p].m1 = a[l];
		t[p].m2 = -1e18;
		t[p].cnt = 1;
		t[p].a.a[0][0] = t[p].a.a[0][1] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build (l, mid, ls(p));
	build (mid + 1, r, rs(p));
	push_up(p);
	return; 
}

void lazy_tag1 (int p, int d) {
	t[p].sum += (t[p].r - t[p].l + 1) * d;
	t[p].m1  += d;
	t[p].m2  += d;
	t[p].add1 += d;
	return;
} 

void lazy_tag2 (int p, int d) {
	t[p].sum += t[p].cnt * d;
	t[p].m1  += d;
	t[p].add2 += d;
	return;
}

void lazy_tag3 (int p, mat now) {
	if (t[p].f1) t[p].add = t[p].add * now;
	else t[p].add = now, t[p].f1 = true;
	return;
}

void lazy_tag4 (int p, mat now) {
	if (t[p].f2) t[p].tag = t[p].tag * now;
	else t[p].tag = now, t[p].f2 = true;
	return;
}

void push_down (int p) {
    
    int mx = max(t[ls(p)].m1, t[rs(p)].m1);
    if (t[ls(p)].m1 == mx) {
		if (t[p].f1) {
			t[ls(p)].a = t[ls(p)].a * t[p].add;
			lazy_tag3 (ls(p), t[p].add);
			if (t[p].f2) {
				lazy_tag4 (ls(p), t[p].tag);
			}
		} else if (t[p].f2) {
			lazy_tag4 (ls(p), t[p].tag);
		}
	} else {
		if (t[p].f2) {
			t[ls(p)].a = t[ls(p)].a * t[p].tag; 
			lazy_tag4 (ls(p), t[p].tag);
		}
	}
	if (t[rs(p)].m1 == mx) {
		if (t[p].f1) {
			t[rs(p)].a = t[rs(p)].a * t[p].add;
			lazy_tag3 (rs(p), t[p].add);
			if (t[p].f2) {
				lazy_tag4 (rs(p), t[p].tag);
			}
		} else if (t[p].f2) {
			lazy_tag4 (rs(p), t[p].tag);
		}
	} else {
		if (t[p].f2) {
			t[rs(p)].a = t[rs(p)].a * t[p].tag;
			lazy_tag4 (rs(p), t[p].tag);
		}
	}
	if (t[ls(p)].m1 == mx) lazy_tag2 (ls(p), t[p].add2);
	if (t[rs(p)].m1 == mx) lazy_tag2 (rs(p), t[p].add2);
	t[p].f1 = t[p].f2 = false;
	lazy_tag1 (ls(p), t[p].add1);
	lazy_tag1 (rs(p), t[p].add1);
	t[p].add1 = t[p].add2 = 0; 
	return;
}

void update (int l, int r, int p, int d) {
	if (l <= t[p].l && t[p].r <= r) {
	    mat now;
		now.a[0][0] = now.a[0][1] = d;
		now.a[1][0] = -1e18, now.a[1][1] = 0;
		t[p].a = t[p].a * now;
		lazy_tag3 (p, now); 
		lazy_tag4 (p, now);
		lazy_tag1 (p, d);
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) update (l, r, ls(p), d);
	if (r >  mid) update (l, r, rs(p), d);
	push_up(p);
	return; 
}

void modify (int l, int r, int p, int d) {
	if (t[p].m1 <= d) return;
	if (l <= t[p].l && t[p].r <= r && t[p].m2 < d) {
	    mat now;
		now.a[0][0] = now.a[0][1] = d - t[p].m1;
		now.a[1][0] = -1e18, now.a[1][1] = 0;
		t[p].a = t[p].a * now;
		lazy_tag3 (p, now); 
		lazy_tag2 (p, d - t[p].m1);
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) modify (l, r, ls(p), d);
	if (r >  mid) modify (l, r, rs(p), d);
	push_up(p);
	return; 
}

int query1 (int l, int r, int p) {
	if (l <= t[p].l && t[p].r <= r) return t[p].sum;
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid && r > mid) return query1 (l, r, ls(p)) + query1 (l, r, rs(p));
	if (l <= mid) return query1 (l, r, ls(p));
	return query1 (l, r, rs(p));
}

int query2 (int l, int r, int p) {
	if (l <= t[p].l && t[p].r <= r) return t[p].m1;
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid && r > mid) return max(query2 (l, r, ls(p)), query2 (l, r, rs(p)));
	if (l <= mid) return query2 (l, r, ls(p));
	return query2 (l, r, rs(p));
}

int query3 (int l, int r, int p) {
	if (l <= t[p].l && t[p].r <= r) return t[p].a.a[0][1];
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid && r > mid) return max(query3 (l, r, ls(p)), query3 (l, r, rs(p)));
	if (l <= mid) return query3 (l, r, ls(p));
	return query3 (l, r, rs(p));
}

signed main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++ i ) scanf("%lld", a + i);
	build (1, n, 1);
	while (m -- ) {
		int o, l, r, k, v;
		scanf("%lld%lld%lld", &o, &l, &r);
		if (o == 1) {
			scanf("%lld", &k);
			update (l, r, 1, k);
		} else if (o == 2) {
			scanf("%lld", &v);
			modify (l, r, 1, v);
		} else if (o == 3) {
			printf("%lld\n", query1 (l, r, 1));
 		} else if (o == 4) {
 			printf("%lld\n", query2 (l, r, 1));
		} else {
			printf("%lld\n", query3 (l, r, 1));
		} 
	}
	return 0; 
}