这道题题目简洁新颖，吸引读者阅读兴趣...
题目
原题目
简要题目
需要你维护长度为n的序列并支持下列操作：
- 区间加法；
- 区间赋值；
- 区间每个 \(a_i\) 变成 \(\max(a_i-t,0)\)；
- 单点询问值
- 单点询问历史最大值
\(n,m≤500000\)，其中 \(m\) 为操作数。
正解
首先考虑，如果这道题没有历史版本我们该怎么做？
其实很简单，这里我就不赘述了 其实是我懒得说 。
那么我们考虑，对于这个 \(5\) 操作，我们应该怎么做？
首先，分析 \(3\) 操作，这是一个很特殊的操作。
对于每个 \(a_i\) ，将 \(a_i\) 修改为 \(\max(a_i-t,0)\)，我们把它写成函数，即
\]
写成一般形式，即
\]
那么，我们可以轻松地画出这个函数的图像：
考虑能否将两个函数 \(f_1(x),f_2(x)\) 的最大值全部合并，成为 \(g(x)\)，即如下图
显然是可行的，具体如何实现请自行思考，如果实在不行，看看代码也好啊。
现在，我们来看这样的函数能不能叠加，即对于 \(f(x)=\max(x+a,b)\)，能不能给 \(a+\Delta\) 或者 \(b+\Delta\)。
显然这也是可行的，即新的 \(f'(x)=\max(x+a+\Delta,b)\) 或者是 \(f'(x)=\max(x+a,b+\Delta)\)。
发现这个函数有叠加性以及能够维护函数最大，发现似乎可以用这样的函数来做这道题，但是，需要对我们的操作进行一些变换：
设标记 \((a,b)\) 表示将 \(x\) 变成 \(\max(a+x,b)\) 。
区间加上 \(a\)：\((a,-\infty)\)；
区间赋值为 \(a\)：\((-\infty,a)\)；
区间每个 \(x\) 变成 \(\max(x-a,0):(-a,0)\)；
合并 \((a,b)\) 与 \((c,d)\)：\((a+c,\max(b+c,d))\)；
假设对一个位置作用的标记对应函数依次为 \(f_1 (x),f_2 (x)\ldots,f_k (x)\)
历史最大值对应函数为 \(\max\{x,f_1 (x),f_2(f_1(x)),……,f_k (f_{k-1}(……f_1(x)))\}\)
如若能维护出该函数，历史最大值即可维护出。
可以发现将两个这样函数取 \(\max\) 后仍然是一个形式一样的函数(见上面的图)。于是历史最大值的函数即可维护。用线段树在每个区间维护当前标记的函数和历史最大值的函数即可，这两个都支持 \(\mathcal O(1)\) 合并。于是复杂度为 \(\mathcal O(n\logn)\)。
#include<cstdio>
#define rep(i,__l,__r) for(signed i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(signed i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair< int,int >
#define Endl putchar('\n')
// #define FILEOI
#define int long long
// #define int unsigned
#ifdef FILEOI
# define MAXBUFFERSIZE 500000
inline char fgetc(){
static char buf[MAXBUFFERSIZE+5],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXBUFFERSIZE,stdin),p1==p2)?EOF:*p1++;
}
# undef MAXBUFFERSIZE
# define cg (c=fgetc())
#else
# define cg (c=getchar())
#endif
template<class T>inline void qread(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)f|=(c=='-');
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
inline int qread(){
int x=0;char c;bool f=0;
while(cg<'0'||'9'<c)f|=(c=='-');
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline int gcd(const int a,const int b){return b?gcd(b,a%b):a;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);
putchar(x%10^48);
}
inline LL mulMod(const LL a,const LL b,const LL mod){//long long multiplie_mod
return ((a*b-(LL)((long double)a/mod*b+1e-8)*mod)%mod+mod)%mod;
}
const int MAXN=5e5;
const int INF=0x3f3f3f3f3f3f3f3fll;
int n,m,val[MAXN+5];
int a[(MAXN<<2)+5][2],b[(MAXN<<2)+5][2];
//a[i][0],b[i][0]:维护当前的 a,b , 若 i 不是叶节点, 那么这就是懒标记
//a[i][1],b[i][1]:维护历史最大版本
#define lc (i<<1)
#define rc (i<<1|1)
#define fff (i>>1)
#define MID ((l+r)>>1)
#define LEQ lc,l,MID
#define REQ rc,MID+1,r
inline void upd(const int i){
a[i][1]=Max(a[i][1],a[i][0]+a[fff][1]);
b[i][1]=Max(b[i][1],Max(b[i][0]+a[fff][1],b[fff][1]));
a[i][0]=Max(a[i][0]+a[fff][0],-INF),b[i][0]=Max(b[i][0]+a[fff][0],b[fff][0]);
}
inline void pushdown(const int i){
upd(lc),upd(rc);
a[i][0]=a[i][1]=0,b[i][0]=b[i][1]=-INF;
}
void modify(const int i,const int l,const int r,const int L,const int R,const int c,const int d){
if(L<=l && r<=R){
a[i][1]=Max(a[i][1],a[i][0]+c);
b[i][1]=Max(b[i][1],Max(b[i][0]+c,d));
a[i][0]=Max(a[i][0]+c,-INF),b[i][0]=Max(b[i][0]+c,d);
return;
}
pushdown(i);
if(L<=MID)modify(LEQ,L,R,c,d);
if(MID<R)modify(REQ,L,R,c,d);
}
int query(const int i,const int l,const int r,const int p,const int o){
if(l==r)return Max(val[p]+a[i][o],b[i][o]);
pushdown(i);
if(p<=MID)return query(LEQ,p,o);
else return query(REQ,p,o);
}
signed main(){
#ifdef FILEOI
freopen("file.in","r",stdin);
freopen("file.out","w",stdout);
#endif
qread(n,m);
rep(i,1,n)qread(val[i]);
int t,l,r,x;
while(m--){
qread(t,l);
if(t<=3){
qread(r,x);
if(t==1)modify(1,1,n,l,r,x,-INF);
else if(t==2)modify(1,1,n,l,r,-x,0);
else modify(1,1,n,l,r,-INF,x);
}
else writc(query(1,1,n,l,t-4),'\n');
}
return 0;
}