Still writing…
Segment Tree Beats!：$2016$ WC 交流课件。
Segment Tree Beats，吉司机线段树，由吉如一在 $2016$ 年国家集训队论文中提出。
在本文中，$\leftarrow$ 表示赋值。
下文中，可能会出现区间最值操作 $\mathcal O(m\log n)$ 的复杂度（单 $\log$），但是似乎于 $2025$ 年末被证伪：若存在区间最值操作，则下界为 $\mathcal O\left(m\log^2n\right)$。
会给出原论文中的复杂度。
区间最值操作
以两道例题引入。
Gorgeous Sequence
给定序列 $a_1,a_2,\cdots,a_n$，维护操作：
- 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow\min(a_i,x)$。
- 对于 $\forall i\in[l,r]$，求 $a_i$ 最大值。
- 对于 $\forall i\in[l,r]$，求 $a_i$ 之和。
我们将「给定 $l,r,x$，对于 $\forall i\in[l,r]$，令 $a_i\leftarrow\min(a_i,x)$」这样的操作称之为「区间最值操作」。即将区间 $[l,r]$ 内的所有数对 $x$ 取 $\min$ 或 $\max$。
根据例题，以下仅讨论区间取 $\min$；区间取 $\max$ 是类似的，并且会在下一部分讨论。
传统线段树似乎无法很好的维护，每次操作中我们的操作对象都是那些大于 $x$ 的数，而不是整个区间。那么我们考虑单独维护区间 $[l,r]$ 内的最大值 $\textit{max}$、最大值的个数 $\textit{cnt}$、次大值 $\textit{max}_2$。（当然，显然还需要维护区间和 $\textit{sum}$）
这些信息都是很好上传维护的。
而区间 $[l,r]$ 对 $x$ 取 $\min$ 时：
-
若 $\textit{max}\leq x$，则取 $\min$ 后肯定不变，无需操作。
-
若 $\textit{max}_2<x<\textit{max}$，则取 $\min$ 后所有的 $\textit{max}$ 都变为了 $x$，且其余所有部分都不变。
更新 $\textit{sum}$ 即令 $\textit{sum}\leftarrow\textit{sum}+\textit{cntMax}(x-\textit{max})$。
之后令 $\textit{max}\leftarrow x$，并且打一个懒标记 $\textit{tagMax}\leftarrow x$ 即可。
-
否则，就暴力递归处理。
原论文中证明不带区间加操作的区间最值为 $\mathcal O(m\log n)$；然而实际上似乎为 $\mathcal O\left(m\log^2n\right)$。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int N=1000000;
int n,a[N+1];
struct segTree{
struct node{
int l,r;
ll sum;
int max,max2,cnt,tag;
}t[N<<2|1];
void up(int p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].max=::max(t[p<<1].max,t[p<<1|1].max);
if(t[p<<1].max>t[p<<1|1].max){
t[p].max=t[p<<1].max;
t[p].cnt=t[p<<1].cnt;
t[p].max2=::max(t[p<<1].max2,t[p<<1|1].max);
}else if(t[p<<1].max==t[p<<1|1].max){
t[p].max=t[p<<1].max;
t[p].cnt=t[p<<1].cnt+t[p<<1|1].cnt;
t[p].max2=::max(t[p<<1].max2,t[p<<1|1].max2);
}else{
t[p].max=t[p<<1|1].max;
t[p].cnt=t[p<<1|1].cnt;
t[p].max2=::max(t[p<<1].max,t[p<<1|1].max2);
}
}
void build(int p,int l,int r){
t[p]={l,r};
t[p].tag=-1;
t[p].max2=-2147483648;
if(l==r){
t[p].sum=t[p].max=a[l];
t[p].cnt=1;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void down(int p){
if(t[p].tag!=-1){
int max=::max(t[p<<1].max,t[p<<1|1].max);
if(max==t[p<<1].max){
t[p<<1].sum-=1ll*t[p<<1].cnt*(t[p<<1].max-t[p].tag);
t[p<<1].max=t[p].tag;
t[p<<1].tag=t[p].tag;
}
if(max==t[p<<1|1].max){
t[p<<1|1].sum-=1ll*t[p<<1|1].cnt*(t[p<<1|1].max-t[p].tag);
t[p<<1|1].max=t[p].tag;
t[p<<1|1].tag=t[p].tag;
}
t[p].tag=-1;
}
}
void chkmin(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
if(t[p].max<=x){
return;
}else if(t[p].max2<x){
t[p].sum-=1ll*t[p].cnt*(t[p].max-x);
t[p].max=x;
t[p].tag=x;
return;
}
}
down(p);
if(l<=t[p<<1].r){
chkmin(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
chkmin(p<<1|1,l,r,x);
}
up(p);
}
int max(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].max;
}
down(p);
int ans=0;
if(l<=t[p<<1].r){
ans=max(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::max(ans,max(p<<1|1,l,r));
}
return ans;
}
ll sum(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].sum;
}
down(p);
ll ans=0;
if(l<=t[p<<1].r){
ans=sum(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans+=sum(p<<1|1,l,r);
}
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
int m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
t.build(1,1,n);
while(m--){
int op,x,y,z;
cin>>op>>x>>y;
switch(op){
case 0:
cin>>z;
t.chkmin(1,x,y,z);
break;
case 1:
cout<<t.max(1,x,y)<<'\n';
break;
case 2:
cout<<t.sum(1,x,y)<<'\n';
}
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 最假女选手
> [Luogu P10639 BZOJ4695 最假女选手](https://www.luogu.com.cn/problem/P10639)
>
> 维护序列 $a_1,a_2,a_3,\cdots,a_n$，实现：
>
> 1. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow a_i+x$。
> 2. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow\max(a_i,x)$。
> 3. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow\min(a_i,x)$。
> 4. 对于 $\forall i\in[l,r]$，求 $a_i$ 之和。
> 5. 对于 $\forall i\in[l,r]$，求 $a_i$ 最大值。
> 6. 对于 $\forall i\in[l,r]$，求 $a_i$ 最小值。
同理，维护 $\textit{sum},\textit{tagAdd},\textit{cntMax},\textit{max},\textit{max}_2,\textit{tagMax},\textit{cntMin},\textit{min},\textit{min}_2,\textit{tagMin}$，共 $10$ 个信息。
钦定加法标记 $\textit{tagAdd}$ 优先，则逻辑和只维护一种是一样的，只是码量会大一些。
同时，进行区间加 $x$ 的时候要将 $\textit{max},\textit{min}$ 加 $x$，如果 $\textit{max}_2,\textit{min}_2,\textit{tagMax},\textit{tagMin}$ 存在的话也要加 $x$。
数集重合
如果一个区间只有 $1\sim 2$ 种数，那么肯定会出现 $\textit{max}=\textit{min}$ 或 $\textit{max}_2=\textit{min},\textit{min}_2=\textit{max}$。
这种时候也要把它一起改掉。
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
#define int ll
typedef long long ll;
constexpr const int N=5e5;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
int n,a[N+1];
struct segTree{
struct node{
int l,r;
ll sum,tagAdd;
int cntMax,cntMin;
ll max,max2,tagMax;
ll min,min2,tagMin;
int size(){
return r-l+1;
}
}t[N<<2|1];
void up(int p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
if(t[p<<1].max>t[p<<1|1].max){
t[p].max=t[p<<1].max;
t[p].cntMax=t[p<<1].cntMax;
t[p].max2=::max(t[p<<1].max2,t[p<<1|1].max);
}else if(t[p<<1].max==t[p<<1|1].max){
t[p].max=t[p<<1].max;
t[p].cntMax=t[p<<1].cntMax+t[p<<1|1].cntMax;
t[p].max2=::max(t[p<<1].max2,t[p<<1|1].max2);
}else{
t[p].max=t[p<<1|1].max;
t[p].cntMax=t[p<<1|1].cntMax;
t[p].max2=::max(t[p<<1].max,t[p<<1|1].max2);
}
if(t[p<<1].min<t[p<<1|1].min){
t[p].min=t[p<<1].min;
t[p].cntMin=t[p<<1].cntMin;
t[p].min2=::min(t[p<<1].min2,t[p<<1|1].min);
}else if(t[p<<1].min==t[p<<1|1].min){
t[p].min=t[p<<1].min;
t[p].cntMin=t[p<<1].cntMin+t[p<<1|1].cntMin;
t[p].min2=::min(t[p<<1].min2,t[p<<1|1].min2);
}else{
t[p].min=t[p<<1|1].min;
t[p].cntMin=t[p<<1|1].cntMin;
t[p].min2=::min(t[p<<1].min,t[p<<1|1].min2);
}
}
void build(int p,int l,int r){
t[p]={l,r};
t[p].tagMax=-inf;
t[p].tagMin=inf;
if(l==r){
t[p].sum=t[p].max=t[p].min=a[l];
t[p].max2=-inf,t[p].min2=inf;
t[p].cntMax=t[p].cntMin=1;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void downAdd(int p,ll x){
t[p].sum+=t[p].size()*x;
t[p].tagAdd+=x;
t[p].max+=x;
if(t[p].max2!=-inf){
t[p].max2+=x;
}
if(t[p].tagMax!=-inf){
t[p].tagMax+=x;
}
t[p].min+=x;
if(t[p].min2!=inf){
t[p].min2+=x;
}
if(t[p].tagMin!=inf){
t[p].tagMin+=x;
}
}
void downMax(int p,ll x){
if(t[p].min>x){
return;
}
t[p].sum+=t[p].cntMin*(x-t[p].min);
t[p].tagMax=x;
if(t[p].max2==t[p].min){
t[p].max2=x;
}
if(t[p].max==t[p].min){
t[p].max=x;
}
t[p].min=x;
if(t[p].tagMin<x){
t[p].tagMin=x;
}
}
void downMin(int p,ll x){
if(t[p].max<=x){
return;
}
t[p].sum+=t[p].cntMax*(x-t[p].max);
t[p].tagMin=x;
if(t[p].min2==t[p].max){
t[p].min2=x;
}
if(t[p].min==t[p].max){
t[p].min=x;
}
t[p].max=x;
if(t[p].tagMax>x){
t[p].tagMax=x;
}
}
void down(int p){
if(t[p].tagAdd){
downAdd(p<<1,t[p].tagAdd);
downAdd(p<<1|1,t[p].tagAdd);
t[p].tagAdd=0;
}
if(t[p].tagMax!=-inf){
downMax(p<<1,t[p].tagMax);
downMax(p<<1|1,t[p].tagMax);
t[p].tagMax=-inf;
}
if(t[p].tagMin!=inf){
downMin(p<<1,t[p].tagMin);
downMin(p<<1|1,t[p].tagMin);
t[p].tagMin=inf;
}
}
void add(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
downAdd(p,x);
return;
}
down(p);
if(l<=t[p<<1].r){
add(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
add(p<<1|1,l,r,x);
}
up(p);
}
void chkmax(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
if(x<=t[p].min){
return;
}else if(x<t[p].min2){
downMax(p,x);
return;
}
}
down(p);
if(l<=t[p<<1].r){
chkmax(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
chkmax(p<<1|1,l,r,x);
}
up(p);
}
void chkmin(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
if(t[p].max<=x){
return;
}else if(t[p].max2<x){
downMin(p,x);
return;
}
}
down(p);
if(l<=t[p<<1].r){
chkmin(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
chkmin(p<<1|1,l,r,x);
}
up(p);
}
ll sum(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].sum;
}
down(p);
ll ans=0;
if(l<=t[p<<1].r){
ans=sum(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans+=sum(p<<1|1,l,r);
}
return ans;
}
ll max(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].max;
}
down(p);
ll ans=-inf;
if(l<=t[p<<1].r){
ans=max(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::max(ans,max(p<<1|1,l,r));
}
return ans;
}
ll min(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].min;
}
down(p);
ll ans=inf;
if(l<=t[p<<1].r){
ans=min(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::min(ans,min(p<<1|1,l,r));
}
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
t.build(1,1,n);
int m;
cin>>m;
while(m--){
int op,l,r,x;
cin>>op>>l>>r;
ll pl;
switch(op){
case 1:
cin>>x;
t.add(1,l,r,x);
break;
case 2:
cin>>x;
t.chkmax(1,l,r,x);
break;
case 3:
cin>>x;
t.chkmin(1,l,r,x);
break;
case 4:
cout<<t.sum(1,l,r)<<'\n';
break;
case 5:
cout<<t.max(1,l,r)<<'\n';
break;
case 6:
cout<<t.min(1,l,r)<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 区间最值转化为区间加减
本质上，我们的做法都是将区间取 $\min$ 转化为了对区间最大值的加减，将区间内的数划分为了最值、非最值来分别维护。
# 区间历史最值
## 相关定义
* 历史最大值：$a_i$ 出现过的最大值。
* 历史最小值：$a_i$ 出现过的最小值。
* 历史版本和：$a_i$ 所有版本的和。
## 可以用懒标记处理的问题
> [Luogu P4314 CPU 监控](https://www.luogu.com.cn/problem/P4314)
>
> 给定序列 $a_1,a_2,\cdots,a_n$，设 $b_1,b_2,\cdots,b_n$ 为其历史最大值，维护操作：
>
> 1. 对于 $\forall i\in[l,r]$，求 $a_i$ 最大值。
> 2. 对于 $\forall i\in[l,r]$，求 $b_i$ 最大值。
> 3. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow a_i+x$。
> 4. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow x$。
先不考虑赋值操作。
那么维护区间最大值 $\textit{max}$，历史最大值 $\textit{hmax}$，加法标记 $\textit{add}$ 是容易想到的。
维护 $\textit{max}$ 时简单的，直接加上 $\textit{add}$ 即可；考虑如何求解 $\textit{hmax}$。
线段树懒标记的特性决定了**懒标记会在一段时间（生存周期）内「停留」在一个位置不变**，同时子树内所有信息不变。那么我们记录生存周期内当前区间最大的 $\textit{add}$ 为 $\textit{hadd}$，则在下传更新时有：
$$
\textit{hmax}=\max(\textit{hmax},\textit{max}+\textit{hadd})
$$
维护 $\textit{hadd}$ 也不难，$\textit{hadd}\leftarrow\max(\textit{hadd},\textit{add}+hx)$ 即可。$\textit{hx}$ 表示增加 $x$ 时，上一层在一个生存周期内增加的最大值。
对于区间覆盖，这其实很简单。因为覆盖之后值都是一样的，反而很好维护。
时间复杂度 $\mathcal O(m\log n)$。（没有区间最值操作，$\mathcal O(m\log n)$ 是正确的。）
参考代码
```cpp //#include<bits/stdc++.h> #include-
using namespace std;
typedef long long ll;
constexpr const int N=1e5,inf=2147483647;
int n,a[N+1];
struct segTree{
struct node{
int l,r;
int max,hmax;
int add,hadd;
int set,hset;
}t[N<<2|1];
void up(int p){
t[p].max=::max(t[p<<1].max,t[p<<1|1].max);
t[p].hmax=::max(t[p<<1].hmax,t[p<<1|1].hmax);
}
void build(int p,int l,int r){
t[p]={l,r};
t[p].set=t[p].hset=-inf;
if(l==r){
t[p].max=t[p].hmax=a[l];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void downAdd(int p,int x,int hx){
t[p].hmax=::max(t[p].hmax,t[p].max+hx);
t[p].max+=x;
if(t[p].set==-inf){
t[p].hadd=::max(t[p].hadd,t[p].add+hx);
t[p].add+=x;
}else{
t[p].hset=::max(t[p].hset,t[p].set+hx);
t[p].set+=x;
}
}
void downSet(int p,int x,int hx){
t[p].hmax=::max(t[p].hmax,hx);
t[p].max=x;
t[p].hset=::max(t[p].hset,hx);
t[p].set=x;
}
void down(int p){
if(t[p].add||t[p].hadd){
downAdd(p<<1,t[p].add,t[p].hadd);
downAdd(p<<1|1,t[p].add,t[p].hadd);
t[p].add=t[p].hadd=0;
}
if(t[p].set!=-inf||t[p].hset!=-inf){
downSet(p<<1,t[p].set,t[p].hset);
downSet(p<<1|1,t[p].set,t[p].hset);
t[p].set=t[p].hset=-inf;
}
}
int max(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].max;
}
int ans=-inf;
down(p);
if(l<=t[p<<1].r){
ans=max(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::max(ans,max(p<<1|1,l,r));
}
return ans;
}
int hmax(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].hmax;
}
int ans=-inf;
down(p);
if(l<=t[p<<1].r){
ans=hmax(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::max(ans,hmax(p<<1|1,l,r));
}
return ans;
}
void add(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
downAdd(p,x,::max(x,0));
return;
}
down(p);
if(l<=t[p<<1].r){
add(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
add(p<<1|1,l,r,x);
}
up(p);
}
void set(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
downSet(p,x,x);
return;
}
down(p);
if(l<=t[p<<1].r){
set(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
set(p<<1|1,l,r,x);
}
up(p);
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
t.build(1,1,n);
int m;
cin>>m;
while(m--){
char op;
int l,r,x;
cin>>op>>l>>r;
switch(op){
case 'Q':
cout<<t.max(1,l,r)<<'\n';
break;
case 'A':
cout<<t.hmax(1,l,r)<<'\n';
break;
case 'P':
cin>>x;
t.add(1,l,r,x);
break;
case 'C':
cin>>x;
t.set(1,l,r,x);
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```
</details>
## 无法用懒标记处理的单点问题
此处「单点问题」除查询单点历史最值外，也包括查询区间历史最小值的最小值、查询区间历史最大值的最大值。因为这两个区间询问的处理方法与单点询问完全相同，所以把它们归入单点问题之中。
> [UOJ169 元旦老人与数列](https://uoj.ac/problem/169)
>
> 设序列 $a_1,a_2,\cdots,a_n$，$b_1,b_2,\cdots,b_n$ 为其历史最小值；维护操作：
>
> 1. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow a_i+x$。
> 2. 对于 $\forall i\in[l,r]$，令 $a_i\leftarrow\max(a_i,x)$。
> 3. 对于 $\forall i\in[l,r]$，求 $a_i$ 最小值。
> 4. 对于 $\forall i\in[l,r]$，求 $b_i$ 最小值。
无法运用懒标记维护，因为取 $\max$ 与历史最小值方向相反，信息无法合并。
但是可以直接运用区间最值操作，将其转化为区间加减后可以类似于上文维护历史最小值的最小值。
时间复杂度 $\mathcal O\left(m\log^2n\right)$。
## 无区间最值操作的区间问题
### 历史最小值之和
对于序列 $a_1,a_2,\cdots,a_n$，设其历史最小值为 $b_1,b_2,\cdots,b_n$；定义 $c_i=a_i-b_i$。
令 $a_i\leftarrow a_i+x$ 时：
* 若 $b_i$ 不变，则令 $c_i\leftarrow c_i+x$。
* 若 $b_i$ 变为了 $a_i$，则令 $c_i\leftarrow0$。
这也就等价于让 $c_i$ 先加 $x$，再与 $0$ 取 $\max$，即 $c_i\leftarrow\max(c_i+x,0)$。
这样就可以 $\mathcal O\left(m\log^2n\right)$ 维护 $a,c$。查询 $b$ 时，二者相减即可得到。
### 历史最大值之和
同理，对于序列 $a_1,a_2,\cdots,a_n$，设其历史最小值为 $b_1,b_2,\cdots,b_n$；定义 $c_i=a_i-b_i$。
令 $a_i\leftarrow a_i+x$，则 $c_i\leftarrow\min(c_i+x,0)$。
时间复杂度 $\mathcal O\left(m\log^2n\right)$。
### 历史版本和之和
设序列 $a_1,a_2,\cdots,a_n$ 的历史版本和为 $b_1,b_2,\cdots,b_n$，当前版本号为 $t$。
定义 $c_i=b_i-t\cdot a_i$。
此时，$a_i\leftarrow a_i+x$ 即令 $c_i\leftarrow c_i-t\cdot x$。
因此可以 $\mathcal O(m\log n)$ 维护 $c$。
## 有区间最值操作的区间问题
先将区间最值操作转化为区间加减，再通过上一节的方法写即可。
