线段树扩展

“黑夜无法掩盖我的锋芒，于深渊之中，你亦无胜算。”

区间最值线段树

区间最值，是指对一个区间 执行 操作。

容易发现，对于 ，如果 ，则不会对答案产生影响，而对于 又一定会产生影响。所以如果我们对一段未知区间进行操作的话，可能会漏改或者错改。那这就意味着我们需要递归到更小的区间，直到满足该操作能够被统一修改。

维护

很容易想到维护 ，当前区间最小值和当前区间最大值，如果 的话，我们可以直接退出，因为 操作在本区间没有任何作用；而如果 的话，那么这个区间的所有值都需要被修改，从而让我们可以正常执行线段树操作。

但事实上，上述方法很容易就会被 掉，卡成 甚至 ，所以我们考虑另外一种维护方式。

吉如一老师在 年的集训队论文中提到过一个有关这个问题的解法，一种通过维护懒标记实现的线段树，后来称为吉司机线段树。

现在以维护 操作为例，我们考虑记录 为区间最大值，并用 记录当前区间最大值的个数，以便我们修改，此时我们再记录 表示区间严格次大值，这里保证 恒成立，用来保证时间复杂度，那么，对于区间 ，会出现以下情况：

• ，那么当前区间一定不会执行 操作。
• ，此时我们修改 ，并同时通过 更新类似于区间和之类的信息，然后打上懒标记，一般而言将此懒标记与区间加的懒标记打在一起，记为 ，这样可以在 的时候方便一些。当然，分开记录懒标记也是正确的。
• ，那我们向下递归，直到满足上述两个条件中的一个。

你可能发现即使这样做依然可以被 ，使每一次操作达到 的复杂度。那我们现在来探究这样做的正确性。

正确性证明

我们维护 表示当前区间的最大值，用 表示 结点的父亲，如果 ，则我们把 删去，这样，整棵树中只会存在至多 个 函数值。

我们此时发现一个性质，一个区间的次大值就是这个区间代表结点 子树内的 。

而对于操作 而言，本质上是修改当前区间的 值，并回收掉当前区间里 的 。以满足 随深度递减的性质。 操作可以视为一个部分区间推平操作，必定会让这个区间不同数的个数减少若干个，而反观维护的其他操作，单点修改每次至多增加一个新的 ，而区间修改并不会增加新的 值，也就是维护过程中至多出现 个 ，而每一次 操作至少会删除一个 （如果没有删除则说明在中途某一步已经返回了），所以整个维护过程中 操作的时间复杂度不会超过 。

所以，维护区间最值的时间复杂度是 的。

但据论文中提到，这个时间复杂度按理来说应该会是 的，但至今并没有构造出能够到达这个上界的数据，大多数数据也都比 慢一点点，所以其时间复杂度可以视作在其之间。

---

历史最值线段树

历史最值，是指对于一般操作而言，在初始的时候将序列 镜像一份至 ，并在每一次操作结束后执行 ，此时将 称为 的历史最大值。

考虑维护当前最大值 和历史最大值 如果每一次操作我们用 直接更新的话是会导致答案偏小的，因为当上一层的区间加懒标记向下传递的时候，操作序列可能为 ，此时 ，但事实上我们应该得到的 应该 才对。

所以考虑将 也进行一份映射，记录历史最大懒标记 ，所以，当进行区间加的时候，我们维护：

$$\begin{align} cval_{p}&\leftarrow\nonumber\max\Big( cval_{p},(val_{p}+ctag_{fa(p)}) \Big)\\ ctag_{p}&\leftarrow\nonumber\max\Big( ctag_{p},(tag_{p}+ctag_{fa(p)}) \Big) \end{align}$$

并在 后将 清空，此时清空的意义在于，如果一次 的前后 可以进行累加，且可能会超过前面某一次操作的 ，这时的 会与后半段的 累加而越过了实际意义上的 ，从而导致我们维护的 偏大，且被传下的 与已知的 比较是没有意义的。下面有一个比较直观的例子：

举例论证

我们的操作序列如下所示：

$$\{+5,-3,+2,\mathrm{pushdown},+2+1\}$$

在 之前，我们维护的 ，此时进行 ，那么 清零，我们这里先假设 不清。然后进行 之后的操作，此时 ， 不变，而 ，就会存在 ，但事实上应该为 ，此时就会出现错误。

而如果我们清空后再下传的时候， 累加为 ,而此时 已经清空，所以 就可以直接被更新成 。

---

例题

区间最值模板题

题目简介

题目名称：

题目来源：

评测链接：https://acm.hdu.edu.cn/showproblem.php?pid=5306

形式化题意：给定一个长度为 的序列 ，要求维护 个操作形如：

1. 对区间 执行 ；
2. 求
3. 求

多测。

数据范围：

有两种维护 的方法，其一是下传 ，意味这个区间应该执行 操作，在更新的时候与父结点以同样的方式更新即可，如果无法更新，就只传 不更新。

第二种是记录 ，把 实际上执行了 ，所以我们将 就可以，这样如果题目里有区间加操作的话就可以将两个懒标记合二为一了。

这道题卡常，需要非常给力的 ，以及我不知道为啥一直过不了，代码就不贴了。

---

历史最值模板题

题目简介

题目名称： 监控

题目来源：不详，疑似

评测链接：https://www.luogu.com.cn/problem/P4314

形式化题意：给定一个长度为 的序列 以及其历史最大值序列 ，维护 个操作形如：

1. 对 加 ；
2. 将 全部修改为 ；
3. 求 的区间最大值；
4. 求 的区间最大值。

数据范围：

考虑需要多维护一个区间覆盖的操作，也就是 标记，这个就需要注意两种 的传递顺序，可能会出现 的顺序，这样两个 是无法被合并的。

考虑一种比较新的合并标记方式，我们现在维护区间加操作，但如果这个区间存在覆盖操作没有被下传，我们把区间加叠到覆盖操作上，将其视作覆盖操作的一部分并下传，否则按照正常的区间加维护，然后就是正常的线段树操作了，记得每次 的时候要把 清空。

AC Code

// ----- Eternally question-----
// Problem: P4314 CPU 监控
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4314
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-10 16:08:29
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
const int INF=0x7f7f7f7f;
int N,Q,a[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	int val,cval,tag,ctag,cov,ccov;
}Tr[MAXN<<2];
inline void Cover(int p,int cov,int ccov)
{
	Tr[p].val=cov,Tr[p].tag=0;
	Tr[p].cov=cov,checkMax(Tr[p].ccov,ccov);
	checkMax(Tr[p].cval,Tr[p].ccov);
}
inline void Add(int p,int tag,int ctag)
{
	if(Tr[p].cov!=-INF) return Cover(p,Tr[p].cov+tag,Tr[p].cov+ctag);
	checkMax(Tr[p].ctag,Tr[p].tag+ctag);
	checkMax(Tr[p].cval,Tr[p].val+ctag);
	Tr[p].val+=tag,Tr[p].tag+=tag;
}
inline void pushUp(int p)
{
	Tr[p].val=std::max(Tr[ls].val,Tr[rs].val);
	Tr[p].cval=std::max(Tr[ls].cval,Tr[rs].cval);
	checkMax(Tr[p].cval,Tr[p].val);
}
inline void pushDown(int p)
{
	Add(ls,Tr[p].tag,Tr[p].ctag),Add(rs,Tr[p].tag,Tr[p].ctag);
	if(Tr[p].cov!=-INF)
	{
		Cover(ls,Tr[p].cov,Tr[p].ccov),Cover(rs,Tr[p].cov,Tr[p].ccov);
		Tr[p].cov=-INF;
	}
	Tr[p].tag=Tr[p].ctag=0;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].tag=Tr[p].ctag=0,Tr[p].cov=-INF;
	if(l==r) return Tr[p].val=Tr[p].cval=a[l],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyAdd(int p,int l,int r,int v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Add(p,v,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyAdd(ls,l,r,v);
	if(mid<r) modifyAdd(rs,l,r,v);
	pushUp(p);
}
void modifyCov(int p,int l,int r,int v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Cover(p,v,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyCov(ls,l,r,v);
	if(mid<r) modifyCov(rs,l,r,v);
	pushUp(p);
}
int queryMax(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1,res=-INF;
	if(l<=mid) checkMax(res,queryMax(ls,l,r));
	if(mid<r) checkMax(res,queryMax(rs,l,r));
	return res;
}
int queryCmax(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].cval;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1,res=-INF;
	if(l<=mid) checkMax(res,queryCmax(ls,l,r));
	if(mid<r) checkMax(res,queryCmax(rs,l,r));
	return res;
}
char Opt[3];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]);
	build(1,1,N);
	read(Q);
	for(int ql,qr,qv;Q--;)
	{
		scanf("%s",Opt+1);read(ql,qr);
		if(Opt[1]=='Q') write(queryMax(1,ql,qr),'\n');
		if(Opt[1]=='A') write(queryCmax(1,ql,qr),'\n');
		if(Opt[1]=='P') read(qv),modifyAdd(1,ql,qr,qv);
		if(Opt[1]=='C') read(qv),modifyCov(1,ql,qr,qv);
	}
	return 0;
}
/*

*/

---

区间最值 I

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P4560

形式化题意：给定一个初始全为 的序列，要求 次操作：

1. 对区间 执行 ；
2. 对区间 执行 。

求最后得到的序列。

数据范围：

这应该是区间最值的祖先了。

考虑操作是 都有，最后还是单点查询，那就只需要下放标记即可。考虑同时维护 ，并将其直接视作区间标记，这样的正确性在于本题仅有单点查询，每次 之后重置当前区间的 ，而避免二度下传，直到叶结点，而至于为什么不需要维护次小，次大，你会发现根本没有必要，我们可以直接处理区间，用当前 更新区间最值，没有任何限制条件。

所以时间复杂度是妥妥的 ，虽然 能过我是没想到的。

AC Code

// ----- Eternally question-----
// Problem: P4560 [IOI2014] Wall 砖墙
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4560
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-07-12 10:20:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e6+10;
const int INF=0x3f3f3f3f;
int N,Q;
#define ls (p<<1)
#define rs (p<<1|1)
struct St
{
	int l,r;
	int mx,mn;
}Tr[MAXN<<2];
inline void chkMx(int p,int v)
{
	if(Tr[p].mx<v) Tr[p].mx=v;
	if(Tr[p].mn<v) Tr[p].mn=v;
}
inline void chkMn(int p,int v)
{
	if(Tr[p].mx>v) Tr[p].mx=v;
	if(Tr[p].mn>v) Tr[p].mn=v;
}
inline void pushDown(int p)
{
	chkMx(ls,Tr[p].mx),chkMx(rs,Tr[p].mx);
	chkMn(ls,Tr[p].mn),chkMn(rs,Tr[p].mn);
	Tr[p].mx=0,Tr[p].mn=INF;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].mn=INF;
	if(l==r) return Tr[p].mx=Tr[p].mn=0,void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void modifyChkmax(int p,int l,int r,int v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return chkMx(p,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyChkmax(ls,l,r,v);
	if(mid<r) modifyChkmax(rs,l,r,v);
}
void modifyChkmin(int p,int l,int r,int v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return chkMn(p,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyChkmin(ls,l,r,v);
	if(mid<r) modifyChkmin(rs,l,r,v);
}
int queryX(int p,int x)
{
	if(Tr[p].l==Tr[p].r) return Tr[p].mx;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	return x<=mid?queryX(ls,x):queryX(rs,x);
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,Q);
	build(1,1,N);
	for(int opt,ql,qr,qv;Q--;)
	{
		read(opt,ql,qr,qv),++ql,++qr;
		if(opt==1) modifyChkmax(1,ql,qr,qv);
		else modifyChkmin(1,ql,qr,qv);
	}
	for(int i=1;i<=N;++i,puts("")) write(queryX(1,i));
	return 0;
}
/*

*/