题目

传送门 to UOJ（看不了可以看下方的简化题意）

思路

简化题意

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

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

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

对于前四个操作

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

• 区间加：新增$\langle x,-\infty\rangle$。
• 区间减：新增$\langle -x,0\rangle$。
• 区间赋值：新增$\langle -\infty,x\rangle$。

如何合并呢？很简单的。

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

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

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

对于第五个操作

将一群操作$\{f_i\}$的最值记为$g(x)$。也就是说，$g(x)=\max\{f_1(x),f_2[f_1(x)],f_3\{f_2[f_1(x)]\},\dots\}$

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

为什么呢？很好证明。

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

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

有了这一重大发现，我们的懒标记就可以派上用场了。我们已经知道了$f=\{ f_1,f_2,f_3,\dots,f_v\}$的最值函数$g_1$，又知道$\{ f_{v+1},f_{v+2},\dots,f_k\}$的最值函数$g_2$，我们就可以说：

$g(x)=\max\{g_1(x),g_2[f(x)]\}$

总结

对于一次添加$f_0,g_0$的操作，我们进行的变换为

$f'=f_0(f),g'=\max[g,g_0(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) = xreturn 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;
}