Description：

$n$ 个数，要求支持区间加，区间减，区间赋值，单点求值，单点求历史最大值。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

显然使用线段树维护历史最大值，同CPU监控那题一样，维护一个区间最值，一个区间标记，一个区间历史最值，一个区间历史最大标记，然后区间赋值不是很好做，因此我们可以换一种标记定义方式 $(a,b)$ 表示先加 $a$ 再和 $b$ 取 $\max$ ，那么第一种操作就是打一个 $(a,0)$ ，第二个操作就是 $(-a,0)$ ，第三个操作就是 $(-\inf,x)$ ，然后再有一个问题就是由于要保存区间历史最大值，所以还涉及到标记的比较大小，在这里可以定义： $\max((xa,xb),(ya,yb))=(\max(xa,ya),\max(xb,yb))$ ，可以发现最后实际上保留了最大的标记，这个可以把两个函数图像画出来就可以直观理解。然后再考虑合并标记： $$ (a,b)+(c,d)=(a+c,\max(b+c,d)) $$ 于是就是一个线段树了。这题由于只有单点求值因此线段树只用来维护标记。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

typedef long long ll;

#define I inline

I ll rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

ll a[MAXN];

#define INF 0x3f3f3f3f3f3fll

struct info

{

	ll a,b;

	void init(){a = 0;b = -INF;}

	I ll f(ll x){return max(x + a,b);}

};

info operator + (info x,info y){return (info){max(x.a + y.a,-INF),max(x.b + y.a,y.b)};}

info max(info x,info y){return (info){max(x.a,y.a),max(x.b,y.b)};}

struct node

{

	int lc,rc;

	info tag,maxtag;

	node(){tag.init();maxtag.init();}

}t[MAXN << 1];

int ptr = 0;

I int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

I void pushdown(int rt)

{

	t[t[rt].lc].maxtag = max(t[t[rt].lc].tag + t[rt].maxtag,t[t[rt].lc].maxtag);

	t[t[rt].rc].maxtag = max(t[t[rt].rc].tag + t[rt].maxtag,t[t[rt].rc].maxtag);

	t[t[rt].lc].tag = t[t[rt].lc].tag + t[rt].tag;

	t[t[rt].rc].tag = t[t[rt].rc].tag + t[rt].tag;

	t[rt].tag.init();t[rt].maxtag.init();

	return;

}

void modify(int rt,int L,int R,info tag,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].tag = t[rt].tag + tag;

		t[rt].maxtag = max(t[rt].maxtag,t[rt].tag);

		return;

	}

	pushdown(rt);

	if(L <= mid)modify(t[rt].lc,L,R,tag,l,mid);

	if(R > mid)modify(t[rt].rc,L,R,tag,mid + 1,r);

	return;

}

#define pi pair<ll,ll>

#define mp make_pair

pi query(int rt,int p,int l,int r)

{

	if(l == r)return mp(t[rt].tag.f(a[l]),t[rt].maxtag.f(a[l]));

	pushdown(rt);

	if(p <= mid)return query(t[rt].lc,p,l,mid);

	else return query(t[rt].rc,p,mid + 1,r);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= n;++i)a[i] = rd();

	build(root,1,n);

	register int opt,l,r;

	register ll x;

	for(register int i = 1;i <= m;++i)

	{

		opt = rd();

		if(opt == 1)l = rd(),r = rd(),x = rd(),modify(root,l,r,(info){x,0},1,n);

		if(opt == 2)l = rd(),r = rd(),x = rd(),modify(root,l,r,(info){-x,0},1,n);

		if(opt == 3)l = rd(),r = rd(),x = rd(),modify(root,l,r,(info){-INF,x},1,n);

		if(opt == 4)l = rd(),printf("%lld\n",query(root,l,1,n).first);

		if(opt == 5)l = rd(),printf("%lld\n",query(root,l,1,n).second);

	}

	return 0;

}