20 pts 求条

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
void read(T &x)
{
	x = 0;
	bool f = false;
	char v = getchar();
	while(v != '-' && (v < '0' || v > '9')) v = getchar();
	if(v == '-') f = true, v = getchar();
	while(v >= '0' && v <= '9') 
	{
		x = (x << 3) + (x << 1) + (v & 15), v = getchar();
	}
	if(f) x = -x;
}
template <typename T>
void write(T x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x < 10) putchar(x | 48);
	else write(x / 10), putchar(x % 10 | 48);
}
const int maxn = 1e6;
const ll inf = 1e18;
int n, q, op, l, r;
ll k;
ll a[maxn + 5];
ll res[maxn * 4 + 5], tag[maxn * 4 + 5];
int ls(int x)
{
	return x << 1;
}
int rs(int x)
{
	return x << 1 | 1; 
}
void pushup(int p)
{
	res[p] = max(res[ls(p)], res[rs(p)]);
}
void pushdown(int p, int s, int t, int mid)
{
	if(tag[p] != -inf)
	{
		tag[ls(p)] = tag[p];
		res[ls(p)] = tag[p];
		tag[rs(p)] = tag[p];
		res[rs(p)] = tag[p];
		tag[p] = -inf;
	}
}
void build(int p, int s, int t)
{
	tag[p] = -inf;
	if(s == t)
	{
		res[p] = a[s];
		return;
	}
	int mid = (s + t) >> 1;
	build(ls(p), s, mid);
	build(rs(p), mid + 1, t);
	pushup(p);
}
void upd1(int p, int s, int t, int l, int r, ll k)
{
	if(l <= s && t <= r) 
	{
		res[p] = k;
		tag[p] = k;
		return;
	}
	if(s == t) return;
	int mid = (s + t) >> 1;
	pushdown(p, s, t, mid);
	if(l <= mid) upd1(ls(p), s, mid, l, r, k);
	if(mid < r) upd1(rs(p), mid + 1, t, l, r, k);
	pushup(p); 
}
void upd2(int p, int s, int t, int l, int r, ll k)
{
	if(l <= s && t <= r) 
	{
		res[p] += k;
		if(tag[p] == -inf) tag[p] = k;
		else tag[p] += k;
		return;
	}
	if(s == t) return;
	int mid = (s + t) >> 1;
	pushdown(p, s, t, mid);
	if(l <= mid) upd2(ls(p), s, mid, l, r, k);
	if(mid < r) upd2(rs(p), mid + 1, t, l, r, k);
	pushup(p); 
}
ll query(int p, int s, int t, int l, int r)
{
	if(l <= s && t <= r) return res[p];
	if(s == t) return -inf;
	int mid = (s + t) >> 1;
	pushdown(p, s, t, mid);
	ll sum = -inf;
	if(l <= mid) sum = query(ls(p), s, mid, l, r);
	if(mid < r) sum = max(sum, query(rs(p), mid + 1, t, l, r));
	return sum;
}
int main(void)
{
	read(n), read(q);
	for(int i = 1; i <= n; ++ i) read(a[i]);
	build(1, 1, n);
	while(q--)
	{
		read(op), read(l), read(r);
		if(op == 1)
		{
			read(k);
			upd1(1, 1, n, l, r, k);
		}
		else if(op == 2)
		{
			read(k);
			upd2(1, 1, n, l, r, k);
		}
		else if(op == 3)
		{
			write(query(1, 1, n, l, r));
			putchar('\n');
		}
	}
	return 0; 
}