本文共 5985 字，大约阅读时间需要 19 分钟。

题目

（看不了可以看下方的简化题意）

思路

简化题意

一个长度为 $n$ 的序列，支持五种操作：

• 区间加：$\forall a\in [l,r],a^{\prime }=a+x$
• 区间减：$\forall a\in [l,r],a^{\prime }=\max (a-x,0)$
• 区间赋值：$\forall a\in [l,r],a^{\prime }=x$
• 单点查询：求 $a_x$ 的值。
• 单点历史最值查询：求历史上任意一个时刻，$a_x$ 达到过的最大值。

数据范围是 $n,m\le 5\times 10^5$ 。

对于前四个操作

将操作写为 $f(x)=\max (x+a,b)$ ，那么对应的懒标记如下。下面用 $⟨a,b⟩$ 表示 $\max (x+a,b)$ 。

• 区间加：新增 $⟨x,-\infty ⟩$ 。原理是 $\forall a\in \mathbb{R},\max (a+x,-\infty )=a+x$
• 区间减：新增 $⟨-x,0⟩$ 。原理是 $\forall a\in \mathbb{R},\max (a-x,0)=\max (a-x,0)$
• 区间赋值：新增 $⟨-\infty ,x⟩$ 。原理是 $\forall a\in \mathbb{R},\max (a-\infty ,x)=x$

如何合并呢？很简单的。

$$\max [\max (x+a,b)+c,d]=\max [x+a+c,\max (b+c,d)]$$

也就是说，$⟨a,b⟩\times ⟨c,d⟩=⟨a+c,\max (b+c,d)⟩$。

注意到我们并没有用到 $x$ 的值，所以其满足结合律。毕竟最后的函数是唯一的！

对于第五个操作

将一群操作 { f i } \{f_i\} { fi​} 的最值记为 $g(x)$ 。也就是说， g ( x ) = max ⁡ { f 1 ( x ) , f 2 [ f 1 ( x ) ] , f 3 { f 2 [ f 1 ( x ) ] } , …   } g(x)=\max\{f_1(x),f_2[f_1(x)],f_3\{f_2[f_1(x)]\},\dots\} g(x)=max{ f1​(x),f2​[f1​(x)],f3​{ f2​[f1​(x)]},…}

这样的 $g(x)$ ，非常抱歉地通知您，还是 $⟨p,q⟩$ 的形式！

为什么呢？很好证明。

$$\max [\max (x+a,b),\max (x+c,d)]=\max [x+\max (a,c),\max (b,d)]$$

也就是说，$⟨a,b⟩+⟨c,d⟩=⟨\max (a,c),\max (b,d)⟩$。

用群论的话来说： { max ⁡ ( a + x , b ) ∣ a , b ∈ R } \{\max(a+x,b)|a,b\in\R\} { max(a+x,b)∣a,b∈R} 在 $\times$（叠加）操作与 $\max$ 操作下构成一个群。

此时，如果我们用函数 $g$ 来维护这个最值，可以预见，这并不是什么麻烦的事情。

我们已经知道了 f = { f 1 , f 2 , f 3 , … , f v } f=\{ f_1,f_2,f_3,\dots,f_v\} f={ f1​,f2​,f3​,…,fv​} 的最值函数 $g_1$ ，又知道 { f v + 1 , f v + 2 , … , f k } \{ f_{v+1},f_{v+2},\dots,f_k\} { fv+1​,fv+2​,…,fk​} 的最值函数 $g_2$ ，我们就可以说：

g ( x ) = max ⁡ { g 1 ( x ) , g 2 [ f ( x ) ] } g(x)=\max\{g_1(x),g_2[f(x)]\} g(x)=max{ g1​(x),g2​[f(x)]}

总结

对于一次添加 f 0 ( x ) = { f i ( x ) } , g 0 ( x ) f_0(x)=\{f_i(x)\},g_0(x) f0​(x)={ fi​(x)},g0​(x) 的操作，我们进行的变换为

$$f^{\prime }(x)=f_0[f(x)],g^{\prime }(x)=\max \{g(x),g_0[f(x)\left]\right\}$$

如果只操作一次 $f$ ，那么 $g(x)=f(x)$ 。也即，集合大小为一的 { f } \{f\} { f} ，其最值函数 $g=f$ 。

代码

#include <cstdio>#include <iostream>#include <vector>#include <algorithm>#include <cstring>using namespace std;inline int readint(){   	int x; scanf("%d",&x); return x;}# define MB template<class T>MB void getMin(T &a,const T &b){    if(b < a) a = b; }MB void getMax(T &a,const T &b){    if(a < b) a = b; }# undef MB // 模板 const int MaxN = 500005;typedef long long int_;const int_ infty = (1ll<<60);int n, m; int_ dnr[MaxN];void input(){   	n = readint(), m = readint();	for(int i=1; i<=n; ++i)		dnr[i] = readint();}struct Pair{    // named "Pair", actually "Function"	int_ one, two; // f(x) = max(x+one,two)	Pair(){    one = two = -infty; }	Pair(int_ O,int_ T){   		one = O, two = T;		if(one < -infty) one = -infty;		if(two < -infty) two = -infty;	}	int_ operator[](const int &x) const {   		if(x == 0) return one;		if(x == 1) return two;		return -infty;	}	static Pair I(){    // f(x) = x		return Pair(0,-infty);	}	int_ operator()(const int &x){   		return max(x+one,two);	}};Pair operator * (const Pair &a,const Pair &b){   	return Pair(a[0]+b[0],max(a[1]+b[0],b[1]));} // 返回的f(x) = fb[fa(x)]Pair operator & (const Pair &a,const Pair &b){   	return Pair(max(a[0],b[0]),max(a[1],b[1]));} // 返回的f(x) = max[fa(x),fb(x)]Pair& operator &= (Pair &a,const Pair &b){   	return a = (a & b); // & 满足交换律}class SegmentTree{   	Pair data[MaxN<<2][2]; // val & maxV	# define id(l,r) ((l+r)|(l!=r))	void change(int o,Pair p[]){   		data[o][1] &= (data[o][0]*p[1]);		data[o][0] = data[o][0]*p[0];	}	# define mid ((l+r)>>1)	void pushDown(int l,int r){   		int o = id(l,r);		change(id(l,mid),data[o]);		change(id(mid+1,r),data[o]);		data[o][0] = data[o][1] = Pair::I();	}public:	void clear(){   		for(int i=0; i<(MaxN<<1); ++i)			data[i][0] = data[i][1] = Pair::I();	}	SegmentTree(){    clear(); }	void modify(int ql,int qr,Pair d[],int l=1,int r=n){   		if(ql <= l and r <= qr)			return change(id(l,r),d);		pushDown(l,r);		if(ql <= mid) modify(ql,qr,d,l,mid);		if(mid < qr) modify(ql,qr,d,mid+1,r);	}	int_ queryNow(int qid,int x,int l=1,int r=n){   		if(l == r) return data[id(l,r)][0](x);		pushDown(l,r);		if(qid <= mid) return queryNow(qid,x,l,mid);		else return queryNow(qid,x,mid+1,r);	}	int_ queryAll(int qid,int x,int l=1,int r=n){   		if(l == r) return data[id(l,r)][1](x);		pushDown(l,r);		if(qid <= mid) return queryAll(qid,x,l,mid);		else return queryAll(qid,x,mid+1,r);	}	# undef mid	# undef id} ppl;Pair gb[2];void solve(){   	ppl.clear();	for(int opt,l,r,x; m; --m){   		opt = readint();		if(opt <= 3)			l = readint(), r = readint(), x = readint();		else x = readint();		if(opt == 1)			gb[0] = gb[1] = Pair(x,-infty);		if(opt == 2)			gb[0] = gb[1] = Pair(-x,0);		if(opt == 3)			gb[0] = gb[1] = Pair(-infty,x);		if(opt <= 3)			ppl.modify(l,r,gb);		if(opt == 4)			printf("%lld\n",ppl.queryNow(x,dnr[x]));		if(opt == 5)			printf("%lld\n",ppl.queryAll(x,dnr[x]));	}}int main(){   	input(), solve();	return 0;}