线段树杂题
CGcgxyXY
·
·
算法·理论
历史和/最值
用来做裸题的话不做介绍。
考虑一类问题,给出一个静态序列,多次询问一个区间所有子区间的信息,例如最值 / 数值种类等信息。
可以对区间的一个端点扫描线,例如右端点。
右端点从左往右扫描,使用线段树维护所有左端点到当前右端点的信息。
信息初始化为单点值,然后右端点扫描的时候更新。
再维护每个点的历史信息,例如历史和或历史最值。
这样一个点 l 的历史信息就是所有左端点为 l,右端点在 [l,r] 内的区间的信息,每个询问只要挂到右端点上然后询问 [l,r] 的历史信息即可。
可能比较抽象,建议配合例题理解。
对于历史信息的维护,简单的方式是直接使用矩阵,或者把矩阵拆成 lazytag。
例如需要维护 val_i 和 his_i。
操作有对 val 区间加、用 val 更新历史和 his,求历史和三种。
形式化地,就是 \forall i \in [l,r],val_i \gets val_i+d,\forall i \in [l,r],his_i \gets his_i+val_i 和 \sum_{i \in [l,r]}his_i 三种操作。
容易发现,这些都是线性变换,可以直接使用 (+,\times) 矩阵维护线段树区间的行向量 \begin{bmatrix}\sum 1&\sum val&\sum his\end{bmatrix}。
考虑修改操作,本质相当于做一次区间乘矩阵。
注意本文的矩阵都是右乘。
区间加的矩阵是 \begin{bmatrix}1&d&0\\0&1&0\\0&0&1\end{bmatrix}。
更新历史和的矩阵是 \begin{bmatrix}1&0&0\\0&1&1\\0&0&1\end{bmatrix}。
然后考虑单位矩阵,容易发现一个矩阵并不是所有位置的值都有必要记录。
有一些位置为常数或者一些位置之间有一定关系,去掉不必要的位置的值之后就得到了数值形式的 lazytag。
例如这里下三角位置都是 0,对角线都为 1,所以只用考虑形式为 \begin{bmatrix}1&a&b\\0&1&c\\0&0&1\end{bmatrix} 的矩阵。
此时 a,b,c 就是 lazytag。
对一个节点打 tag 的时候只需要模拟一下,按照矩乘的规则直接乘上去即可。
但是需要注意,下传标记的时候需要考虑下传的顺序,对于只有上三角有值的矩阵,可以直接从右往左依次下传,同一列之间没有先后顺序。
下传的判断可以简单判断这些值是否与单位矩阵相同,也可以每个节点存一个 flg。
每次打完 tag 令 flg \gets 1,下传的时候判断一下,如果 flg=1 那么下传并更新 flg=0。
对于历史最值,我没找到类似的题,但是这里有一道裸题,可以拿来给矩阵或者拆 tag 练手。
:::info[Hint]
使用 (\max,+) 矩阵维护。
:::
P3246 [HNOI2016] 序列
Description
给出长度为 n 的序列 a_1,a_2,\dots,a_n。
#### Solution
离线,扫描 $r$,维护 $val_l=\min_{i=l}^r a_i$,$his_l$ 为 $val_l$ 的历史和。
可以用单调栈维护,栈里面是当前的所有后缀最小值 $stk_i$。
每次 $r$ 增加之后,先更新单调栈和线段树,然后回答询问。
认为 $stk_0=0$,弹栈的时候 $i \in (stk_{top-1},stk_{top}]$ 的 $val_i$ 会从 $a_{stk_{top}}$ 变成 $a_r$,需要做区间加 $a_r-a_{stk_{top}}$。
由于每次更新之前 $stk_{top}=r-1$,初始化 $val_r=a_r$ 可以减少一次特判。
加完之后更新历史和,$\forall i \in[1,r],his_i \gets his_i+val_i$。
然后回答所有 $r$ 上面的询问,$\sum_{i=l}^r his_i$ 就是答案。
:::info[拆矩阵]
操作就是对 $val$ 区间加和求 $val$ 的历史和 $his$,同上面的介绍。
:::
建树线性,单调栈以及历史和的更新有 $O(n)$ 次,查询 $O(q)$ 次。
因此时间复杂度是 $O((n+q)\log n)$,空间 $O(n+q)$。
#### Code
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=1e5+5;
int n,q;
int a[N];
struct node{
int len;
ll sum,hsum;
ll ls;
ll lh,sh;
void muls(ll x){
sum+=x*len;
ls+=x;
}
void mulh(ll x,ll y){
hsum+=x*len+y*sum;
lh+=x+ls*y;
sh+=y;
}
}t[N<<2];
#define lc p<<1
#define rc p<<1|1
#define mid ((pl+pr)>>1)
void up(int p){
t[p].sum=t[lc].sum+t[rc].sum;
t[p].hsum=t[lc].hsum+t[rc].hsum;
}
void down(int p){
if(t[p].lh||t[p].sh){
t[lc].mulh(t[p].lh,t[p].sh);
t[rc].mulh(t[p].lh,t[p].sh);
t[p].lh=t[p].sh=0;
}
if(t[p].ls){
t[lc].muls(t[p].ls);
t[rc].muls(t[p].ls);
t[p].ls=0;
}
}
void build(int p,int pl,int pr){
t[p].len=pr-pl+1;
if(pl==pr){
t[p].sum=a[pl];
return;
}
build(lc,pl,mid);
build(rc,mid+1,pr);
up(p);
}
void add(int p,int pl,int pr,int l,int r,int x){
if(l<=pl&&pr<=r) return t[p].muls(x);
down(p);
if(l<=mid) add(lc,pl,mid,l,r,x);
if(r>mid) add(rc,mid+1,pr,l,r,x);
up(p);
}
void apl(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].mulh(0,1);
down(p);
if(l<=mid) apl(lc,pl,mid,l,r);
if(r>mid) apl(rc,mid+1,pr,l,r);
up(p);
}
ll sum(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].hsum;
ll res=0;
down(p);
if(l<=mid) res+=sum(lc,pl,mid,l,r);
if(r>mid) res+=sum(rc,mid+1,pr,l,r);
return res;
}
vector <pair<int,int>> qy[N];
ll ans[N];
int stk[N],top;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
rep(i,1,n) cin>>a[i];
build(1,1,n);
rep(i,1,q){
int l,r;
cin>>l>>r;
qy[r].push_back({l,i});
}
rep(i,1,n){
while(top&&a[stk[top]]>a[i]) add(1,1,n,stk[top-1]+1,stk[top],a[i]-a[stk[top]]),--top;
stk[++top]=i;
apl(1,1,n,1,i);
for(auto [l,id]:qy[i]) ans[id]=sum(1,1,n,l,i);
}
rep(i,1,q) cout<<ans[i]<<'\n';
return 0;
}
```
:::
### [P10822 [EC Final 2020] Prof. Pang's sequence](https://www.luogu.com.cn/problem/P10822)
#### Description
给出长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。
$q$ 次询问,每次给出 $l,r$,求 $\sum_{[x,y] \subseteq [l,r]}[\operatorname{cnt}(x,y) \bmod 2 = 1]$。
$\operatorname{cnt}(x,y)$ 表示 $[x,y]$ 区间内数值的种类数。
#### Solution
先考虑维护所有 $val_l=\operatorname{cnt}(l,r)$。
拆成二维数点,令 $pre_i =\max_{j<i \land a_i=a_j}j$,那么 $\operatorname{cnt}(l,r)=\sum_{i=l}^r [pre_i \geq l]$。
所以 $r$ 增加之后,$(pre_r,r]$ 的种类数会增加 $1$,是一个区间加的形式。
初始化可以不用赋值,让所有的 $val_i=0$,这样区间加的时候包含 $r$,可以减少多余的空区间特判和初始化。
然后可以发现 $\sum[\operatorname{cnt}(x,y) \bmod 2 = 1]=\sum (\operatorname{cnt}(x,y) \bmod 2)$,所以只需要维护 $01$ 序列,区间加 $1$ 变成区间取反。
这样操作就只有 $\sum val \gets len -\sum val,\sum his \gets \sum his+\sum val$ 和查询 $\sum his$。
都是线性变换的形式,容易维护。
:::info[拆矩阵]
线段树每个节点维护行向量 $\begin{bmatrix}\sum 1&\sum val&\sum his\end{bmatrix}$。
三种操作分别为 $\forall i \in [l,r],val_i \gets 1-val_i$,$\forall i \in [l,r],his_i \gets his_i+val_i$,$\sum_{i \in [l,r]}his_i$。
仍然是线性变换,两个修改乘上的矩阵分别为 $\begin{bmatrix}1&1&0\\0&-1&0\\0&0&1\end{bmatrix}$ 和 $\begin{bmatrix}1&0&0\\0&1&1\\0&0&1\end{bmatrix}$。
再考察单位矩阵,发现 tag 矩阵都是 $\begin{bmatrix}1&a&c\\0&b&d\\0&0&1\end{bmatrix}$ 的形式,于是就拆完了。
:::
时间 $O((n+q) \log n)$,空间 $O(n+q)$。
#### Code
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N=5e5+5;
int n,q;
int a[N];
int pos[N];
vector <pair<int,int>> qy[N];
ll ans[N];
struct node{
int len,sum;
ll his;
int a,b,c,d;
bool flg;
void tag(int x,int y,int z,int t){
his+=1LL*z*len+1LL*t*sum;
sum=x*len+y*sum;
c+=a*t+z;
d+=b*t;
a=a*y+x;
b*=y;
flg=1;
}
}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
void build(int p,int pl,int pr){
t[p].len=pr-pl+1;
t[p].b=1;
if(pl==pr) return;
build(ls,pl,mid);
build(rs,mid+1,pr);
}
void down(int p){
if(t[p].flg){
t[ls].tag(t[p].a,t[p].b,t[p].c,t[p].d);
t[rs].tag(t[p].a,t[p].b,t[p].c,t[p].d);
t[p].a=t[p].c=t[p].d=0;t[p].b=1;
t[p].flg=0;
}
}
void up(int p){
t[p].sum=t[ls].sum+t[rs].sum;
t[p].his=t[ls].his+t[rs].his;
}
void add(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].tag(1,-1,0,0);
down(p);
if(l<=mid) add(ls,pl,mid,l,r);
if(r>mid) add(rs,mid+1,pr,l,r);
up(p);
}
void apl(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].tag(0,1,0,1);
down(p);
if(l<=mid) apl(ls,pl,mid,l,r);
if(r>mid) apl(rs,mid+1,pr,l,r);
up(p);
}
ll sum(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].his;
down(p);
ll res=0;
if(l<=mid) res+=sum(ls,pl,mid,l,r);
if(r>mid) res+=sum(rs,mid+1,pr,l,r);
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
rep(i,1,n) cin>>a[i];
cin>>q;
rep(i,1,q){
int l,r;
cin>>l>>r;
qy[r].push_back({l,i});
}
build(1,1,n);
rep(r,1,n){
add(1,1,n,pos[a[r]]+1,r);
apl(1,1,n,1,r);
pos[a[r]]=r;
for(auto [l,i]:qy[r]) ans[i]=sum(1,1,n,l,r);
}
rep(i,1,q) cout<<ans[i]<<'\n';
return 0;
}
```
:::
### [P8868 [NOIP2022] 比赛](https://www.luogu.com.cn/problem/P8868)
#### Description
给出长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_n$。
$q$ 次询问,每次给出 $l,r$,求 $\sum_{[x,y] \subseteq [l,r]}(\max_{i=x}^y a_i)(\max_{i=x}^y b_i) \bmod 2^{64}$。
#### Solution
取模是简单的,使用 `unsigned long long` 自然溢出即可。
最值的维护仍然可以用单调栈,不过查询内容变成了两个序列上面最值的积,要麻烦一些。
仍然使用单调栈和历史和线段树,考虑如何维护。
维护 $mxa_l=\max_{i=l}^r a_i,mxb_l=\max_{i=l}^r b_i,val_l=mxa_l mxb_l,his_l =\sum val_l$。
单调栈需要对 $mxa,mxb$ 做区间加,以及更新 $his$ 和查询 $his$ 区间和。
考虑更新 $mxa,mxb$ 时如何更新 $val$。
$\forall i \in [x,y],mxa_i \gets mxa_i+d$,于是 $mxa_i \cdot mxb_i \gets (mxa_i+d) mxb_i=mxa_imxb_i+mxb_i\cdot d$,即 $val_i \gets val_i+b_i\cdot d$。
$mxb$ 区间加同理。
发现还是线性组合,仍然可以简单维护。
和第一个例题类似,由于更新时单调栈只维护了 $[1,r)$,初始化 $mxa_i=a_i,mxb_i=b_i,val_i=a_i \cdot b_i$ 会比较方便。
不过矩阵常数比较大,建议拆掉。
但是写矩阵也可以卡过去。
:::info[拆矩阵]
需要维护 $mxa,mxb$ 区间加,$his \gets his+mxa \cdot mxb$,$his$ 区间和。
每个节点维护 $\begin{bmatrix}\sum 1&\sum mxa&\sum mxb&\sum val&\sum his\end{bmatrix}$ 行向量。
$mxa$ 区间加相当于 $mxa\gets mxa+d,val \gets val+d\cdot mxb$。
矩阵为 $\begin{bmatrix}1&d&0&0&0\\0&1&0&0&0\\0&0&1&d&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}$。
同理,可以得到 $mxb$ 的区间加对应的矩阵 $\begin{bmatrix}1&0&d&0&0\\0&1&0&d&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}$。
更新历史和的矩阵是 $\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&1\\0&0&0&0&1\end{bmatrix}$。
可以发现最终一个 tag 矩阵的形式为 $\begin{bmatrix}1&ta&tb&ta\cdot tb&hl\\0&1&0&tb&ha\\0&0&1&ta&hb\\0&0&0&1&hs\\0&0&0&0&1\end{bmatrix}$。
于是 lazytag 就为 $ta,tb,hl,ha,hb,hs$。
:::
时间 $O((n+q)\log n)$,空间 $O(n+q)$。
#### Code
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ui unsigned int
#define ull unsigned long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=2.5e5+5;
struct node{
int len;
ull sa,sb;
ull sm;
ull hsm;
ull ta,tb;
ull hl,ha,hb,hs;
void adda(ull x){
ta+=x;
sa+=x*len;
sm+=x*sb;
}
void addb(ull x){
tb+=x;
sb+=x*len;
sm+=x*sa;
}
void addh(){
hsm+=sm;
++hs;
ha+=tb;
hb+=ta;
hl+=ta*tb;
}
void addh(ull l,ull a,ull b,ull s){
hs+=s;
ha+=a+tb*s;
hb+=b+ta*s;
hl+=l+a*ta+b*tb+s*ta*tb;
hsm+=l*len+sa*a+sb*b+sm*s;
}
}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
inline void up(int p){
t[p].sa=t[ls].sa+t[rs].sa;
t[p].sb=t[ls].sb+t[rs].sb;
t[p].sm=t[ls].sm+t[rs].sm;
t[p].hsm=t[ls].hsm+t[rs].hsm;
}
inline void down(int p){
if(t[p].hs||t[p].hl||t[p].ha||t[p].hb){
t[ls].addh(t[p].hl,t[p].ha,t[p].hb,t[p].hs);
t[rs].addh(t[p].hl,t[p].ha,t[p].hb,t[p].hs);
t[p].hl=t[p].ha=t[p].hb=t[p].hs=0;
}
if(t[p].ta){
t[ls].adda(t[p].ta);
t[rs].adda(t[p].ta);
t[p].ta=0;
}
if(t[p].tb){
t[ls].addb(t[p].tb);
t[rs].addb(t[p].tb);
t[p].tb=0;
}
}
inline void adda(int p,int pl,int pr,int l,int r,ull x){
if(l<=pl&&pr<=r) return t[p].adda(x);
down(p);
if(l<=mid) adda(ls,pl,mid,l,r,x);
if(r>mid) adda(rs,mid+1,pr,l,r,x);
up(p);
}
inline void addb(int p,int pl,int pr,int l,int r,ull x){
if(l<=pl&&pr<=r) return t[p].addb(x);
down(p);
if(l<=mid) addb(ls,pl,mid,l,r,x);
if(r>mid) addb(rs,mid+1,pr,l,r,x);
up(p);
}
inline void addh(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].addh();
down(p);
if(l<=mid) addh(ls,pl,mid,l,r);
if(r>mid) addh(rs,mid+1,pr,l,r);
up(p);
}
inline ull query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p].hsm;
ull res=0;
down(p);
if(l<=mid) res+=query(ls,pl,mid,l,r);
if(r>mid) res+=query(rs,mid+1,pr,l,r);
return res;
}
int T,n,q;
int a[N],b[N];
void build(int p,int pl,int pr){
t[p].len=pr-pl+1;
if(pl==pr){
t[p].sa=a[pl],t[p].sb=b[pl],t[p].sm=1ULL*a[pl]*b[pl];
return;
}
build(ls,pl,mid);
build(rs,mid+1,pr);
up(p);
}
vector <pair<int,int>> qy[N];
ull ans[N];
int s1[N],t1,s2[N],t2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T>>n;
rep(i,1,n) cin>>a[i];
rep(i,1,n) cin>>b[i];
cin>>q;
rep(i,1,q){
int l,r;
cin>>l>>r;
qy[r].push_back({l,i});
}
build(1,1,n);
rep(i,1,n){
while(t1&&a[s1[t1]]<a[i]) adda(1,1,n,s1[t1-1]+1,s1[t1],a[i]-a[s1[t1]]),--t1;
while(t2&&b[s2[t2]]<b[i]) addb(1,1,n,s2[t2-1]+1,s2[t2],b[i]-b[s2[t2]]),--t2;
s1[++t1]=i,s2[++t2]=i;
addh(1,1,n,1,i);
for(auto [l,id]:qy[i]) ans[id]=query(1,1,n,l,i);
}
rep(i,1,q) cout<<ans[i]<<'\n';
return 0;
}
```
:::
### 习题
#### [P10637 BZOJ4262 Sum](https://www.luogu.com.cn/problem/P10637)
:::info[Hint]
将询问的 4-side 矩形差分成四个 2-side 矩形,然后就可以直接做。
离线,扫描右端点 $r$,线段树维护所有左端点 $l$ 到 $r$ 的 $\max -\min$ 以及历史和。
用两个单调栈维护最值,右端点变化的时候更新。
:::
#### [P9990 [Ynoi Easy Round 2023] TEST_90](https://www.luogu.com.cn/problem/P9990)
:::info[Hint]
P10822 双倍经验。
由于数据范围大了一点,可能有一定常数要求。
:::
#### [CF997E Good Subsegments](https://www.luogu.com.cn/problem/CF997E)
:::info[Hint]
区间是好的相当于 $\max-\min=r-l$。
由于是排列,有 $\max-\min \geq r-l$。
也就是 $\max-\min+l-r \geq 0$。
维护所有 $\max-\min+l-r$ 的最小值和最小值个数,最小值为 $0$ 时更新历史和。
:::
## 单侧递归
有时候需要维护的信息无法简单合并,可以在线段树上单侧递归解决。
### [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)
#### Description
给定一个长度为 $n$ 的序列 $y_1,y_2,\dots,y_n$。
有 $m$ 次单点修改,每次修改之后你需要求出 $\frac{y_i}{i}$ 的严格前缀最大值个数。
#### Solution
线段树维护区间的最大值 $mx$ 和严格前缀最大值个数 $cnt$。
容易发现上传时需要完成以下操作:求出右区间的前面已经有了一个左区间的最大值 $mx_{ls}$ 之后右区间的严格前缀最大值个数。
这里使用 $f(p,v)$ 表示在区间 $p$ 前面已经有了最值 $v$ 的情况下,区间 $p$ 内严格最大值的个数。
可以发现右区间被更新的前缀最大值只会是一个前缀,于是可以直接在右子树上二分。
如果到达了叶子,判断单点并返回。
记当前区间 $[l,r]$ 的节点为 $p$,两个子区间分别为 $ls,rs$。
记当前区间内前缀最值 $\max_{j=l}^i a_j<v$ 的位置 $j$ 为“被更新的位置”,最后一个被更新的位置为 $pos$。
如果 $mx_{ls} > v$,说明 $pos$ 在左区间,此时右区间贡献不变,递归左区间计算。
需要注意的是,右区间贡献不是 $cnt_{rs}$ 而是 $cnt_p-cnt_{ls}$,因为 $cnt_{rs}$ 的前缀是 $(mid,i]$,会得到错误的结果。
如果 $mx_{ls} \leq v$,说明 $pos$ 在右区间,左区间没有贡献。
此时左区间对于最值也没有贡献,可以直接递归右区间。
有可能会存在 $pos=mid$ 的情况,但是由于特判了单点所以没有影响。
显然的,由于每次只递归一侧,一次单侧递归的复杂度是线段树的树高,为 $O(\log n)$。
由于每一次上传都会单侧递归一次,时间复杂度为 $O(n\log n+m \log^2 n)$,空间 $O(n)$。
需要考虑一个前缀没有建造楼房的情况,可以加入 $y_0=0$,线段树维护 $[0,n]$,并使 $0$ 的位置为 $\frac{0}{1}$,这样 $0$ 自然是一个前缀最值位置,输出答案的时候减去 $1$ 即可。
#### Code
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N=1e5+5;
int n,m;
struct frac{int a,b;}a[N];
bool operator < (const frac &x,const frac &y){return 1ll*x.a*y.b<1ll*y.a*x.b;}
bool operator > (const frac &x,const frac &y){return 1ll*x.a*y.b>1ll*y.a*x.b;}
frac max(const frac &x,const frac &y){return x>y?x:y;}
struct node{
frac mx;
int cnt;
}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
int calc(int p,int pl,int pr,frac x){
if(pl==pr) return t[p].mx>x;
if(t[ls].mx>x) return t[p].cnt-t[ls].cnt+calc(ls,pl,mid,x);
return calc(rs,mid+1,pr,x);
}
void up(int p,int pl,int pr){
t[p].mx=max(t[ls].mx,t[rs].mx);
t[p].cnt=t[ls].cnt+calc(rs,mid+1,pr,t[ls].mx);
}
void build(int p,int pl,int pr){
if(pl==pr) t[p]={a[pl],1};
else build(ls,pl,mid),build(rs,mid+1,pr),up(p,pl,pr);
}
void upd(int p,int pl,int pr,int x){
if(pl==pr) return void(t[p].mx=a[pl]);
x<=mid?upd(ls,pl,mid,x):upd(rs,mid+1,pr,x);
up(p,pl,pr);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
rep(i,1,n) a[i]={0,i};
a[0]={0,1};
build(1,0,n);
while(m--){
int x;
cin>>x;
cin>>a[x].a;
upd(1,0,n,x);
cout<<t[1].cnt-1<<'\n';
}
return 0;
}
```
:::
### [P17826 [COCI 2026/2027 #1] 水 / Voda](https://www.luogu.com.cn/problem/P17826)
#### Description
维护一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。
有 $m$ 次操作,分为 $5$ 种类型。
1. 给出 $p,x$,$a_p \gets x$。
2. 给出 $l,r,x$,$\forall i \in [l,r]$,$a_i \gets x$。
3. 给出 $l,r,x$,$\forall i \in [l,r]$,$a_i \gets a_i+x$。
4. 给出 $l,r$,求 $\sum_{i=l}^r[\max_{j=l}^ia_j=a_i \lor \max_{j=i}^r a_j=a_i]$。
5. 给出 $l,r$,求 $\sum_{i=l}^r \min(\max_{j=l}^ia_j,\max_{j=i}^r a_j)-a_i$。
#### Solution
前三种都是平凡的,关注后两种。
对于区间 $[l,r]$,记 $p_i=\max_{j=l}^i a_j$,$s_i=\max_{j=i}^r a_j$,$mx=\max_{j=l}^r a_j$。
##### 4
考虑容斥为 $\sum_{i=l}^r[p_i=a_i]+\sum_{i=l}^r[s_i=a_i]-\sum_{i=l}^r[p_i=a_i \land s_i=a_i]$。
由于 $[l,i] \cup [i,r]=[l,r]$,$p_i=a_i \land s_i=a_i$ 相当于 $a_i=mx$。
式子变为 $\sum_{i=l}^r[p_i=a_i]+\sum_{i=l}^r[s_i=a_i]-\sum_{i=l}^r[a_i=mx]$。
需要维护区间最大值,最大值个数,前后缀非严格最大值个数。
##### 5
考虑容斥为 $\sum_{i=l}^r s_i+p_i-\max(s_i,p_i)-a_i$。
由于 $[l,i] \cup [i,r]=[l,r]$,$\max(s_i,p_i)=mx$。
式子变为 $\sum_{i=l}^rs_i+p_i-a_i-mx=\sum_{i=l}^r s_i+\sum_{i=l}^r p_i-\sum_{i=l}^r a_i-(r-l+1)mx$。
需要维护区间最大值,区间和与前后缀最大值和。
##### 维护
线段树的每个节点需要维护以下信息:
长度 $len$,区间最大值 $mx$,最大值个数 $c$,区间和 $sum$,前缀最值信息 $pre$,后缀最值信息 $suf$。
前四个都很好维护。
然后考虑三种操作对最值信息 $(cnt,sum)$ 的影响。
单点修改是简单的。
区间加 $d$ 会改变最值和,但是最值数量不变,$sum \gets sum +d \cdot len$。
区间赋值为 $v$ 会同时改变这两种值,$cnt \gets len,sum \gets v \cdot len$。
所以修改是简单的,仍然可以使用 lazytag。
考虑如何合并两个区间的信息。
以合并 $pre$ 为例,$suf$ 同理。
需要求出左区间最值对右区间信息的的贡献。
定义函数 $f(p,x)$ 为线段树节点 $p$ 的区间左侧有最值 $x$ 的前缀最值信息。
考虑如何计算 $f(p,x)$。
被更新的前缀最值显然还是一段前缀,所以仍然可以在右边区间的子树上二分找到最后一个被更新的位置 $pos$。
如果 $p$ 是叶子,直接特判并返回 $([a_p \geq x],\max(a_p,x))$。
否则记 $p$ 的左右儿子分别为 $ls,rs$。
如果 $mx_{ls} \geq x$,说明 $pos$ 在左区间,作差得到右区间贡献,然后递归左区间计算。
如果 $mx_{ls} < x$,说明 $pos$ 在右区间,左区间贡献为 $(len_{ls},len_{ls} \cdot x)$,然后递归右区间计算。
由于有 lazytag,判断之前需要先下传标记,
查询的时候需要注意查询顺序和目前查询的部分对 $pre$ 或 $suf$ 的影响。
$pre$ 需要从左往右查询,并记录当前查询过区间的最大值 $val$,一个被完全覆盖的区间的贡献为 $f(p,val)$。
$suf$ 的查询同理。
可以分析出时间复杂度是 $O(n\log n+m \log^2 n)$,空间 $O(n)$。
#### Code
由于保证 $h_i \in [0,10^9]$,$mx$ 可以使用 `int`,而其他的区间和信息都要使用 `long long`。
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=2e5+5;
int n,q;
int a[N];
#define pil pair<int,ll>
#define fi first
#define se second
inline pil operator + (const pil &x,const pil &y){return {x.fi+y.fi,x.se+y.se};}
inline pil operator - (const pil &x,const pil &y){return {x.fi-y.fi,x.se-y.se};}
struct node{
int len;
ll sum;
int mx,c;
pil pre,suf;
int at,ct;
void add(ll x){
sum+=x*len;
mx+=x;
pre.se+=x*len;
suf.se+=x*len;
at+=x;
}
void chg(ll x){
sum=x*len;
mx=x;
c=len;
pre=suf={len,sum};
at=0;
ct=x;
}
}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
void down(int p){
if(t[p].ct!=-1){
t[ls].chg(t[p].ct);
t[rs].chg(t[p].ct);
t[p].ct=-1;
}
if(t[p].at){
t[ls].add(t[p].at);
t[rs].add(t[p].at);
t[p].at=0;
}
}
pil Pre(int p,int x){
if(t[p].len==1) return {t[p].mx>=x,max(t[p].mx,x)};
down(p);
if(t[ls].mx>=x) return Pre(ls,x)+t[p].pre-t[ls].pre;
return Pre(rs,x)+(pil){0,1ll*x*t[ls].len};
}
pil Suf(int p,int x){
if(t[p].len==1) return {t[p].mx>=x,max(t[p].mx,x)};
down(p);
if(t[rs].mx>=x) return Suf(rs,x)+t[p].suf-t[rs].suf;
return Suf(ls,x)+(pil){0,1ll*x*t[rs].len};
}
void up(int p){
t[p].mx=max(t[ls].mx,t[rs].mx);
t[p].sum=t[ls].sum+t[rs].sum;
t[p].c=(t[ls].mx>=t[rs].mx?t[ls].c:0)+(t[rs].mx>=t[ls].mx?t[rs].c:0);
t[p].pre=Pre(rs,t[ls].mx)+t[ls].pre;
t[p].suf=Suf(ls,t[rs].mx)+t[rs].suf;
}
void build(int p,int pl,int pr){
t[p].len=pr-pl+1;
t[p].ct=-1;
if(pl==pr) t[p]={1,a[pl],a[pl],1,{1,a[pl]},{1,a[pl]},0,-1};
else build(ls,pl,mid),build(rs,mid+1,pr),up(p);
}
void add(int p,int pl,int pr,int l,int r,int x){
if(l<=pl&&pr<=r) return t[p].add(x);
down(p);
if(l<=mid) add(ls,pl,mid,l,r,x);
if(r>mid) add(rs,mid+1,pr,l,r,x);
up(p);
}
void updt(int p,int pl,int pr,int x,int v){
if(pl==pr){t[p]={1,v,v,1,{1,v},{1,v},0,-1};return;}
down(p);
x<=mid?updt(ls,pl,mid,x,v):updt(rs,mid+1,pr,x,v);
up(p);
}
void cov(int p,int pl,int pr,int l,int r,int x){
if(l<=pl&&pr<=r) return t[p].chg(x);
down(p);
if(l<=mid) cov(ls,pl,mid,l,r,x);
if(r>mid) cov(rs,mid+1,pr,l,r,x);
up(p);
}
pil qpre(int p,int pl,int pr,int l,int r,int &mx){
if(l<=pl&&pr<=r){
pil res=Pre(p,mx);
mx=max(mx,t[p].mx);
return res;
}
down(p);
pil res={0,0};
if(l<=mid) res=res+qpre(ls,pl,mid,l,r,mx);
if(r>mid) res=res+qpre(rs,mid+1,pr,l,r,mx);
return res;
}
pil qsuf(int p,int pl,int pr,int l,int r,int &mx){
if(l<=pl&&pr<=r){
pil res=Suf(p,mx);
mx=max(mx,t[p].mx);
return res;
}
down(p);
pil res={0,0};
if(r>mid) res=res+qsuf(rs,mid+1,pr,l,r,mx);
if(l<=mid) res=res+qsuf(ls,pl,mid,l,r,mx);
return res;
}
struct tmp{
int mx,cnt;
ll sum;
};
tmp operator + (const tmp &x,const tmp &y){return {max(x.mx,y.mx),(x.mx>=y.mx?x.cnt:0)+(y.mx>=x.mx?y.cnt:0),x.sum+y.sum};}
tmp query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return {t[p].mx,t[p].c,t[p].sum};
down(p);
if(r<=mid) return query(ls,pl,mid,l,r);
if(l>mid) return query(rs,mid+1,pr,l,r);
return query(ls,pl,mid,l,r)+query(rs,mid+1,pr,l,r);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
rep(i,1,n) cin>>a[i];
build(1,1,n);
while(q--){
int op,l,r,x;
cin>>op;
if(op==1) cin>>l>>x,updt(1,1,n,l,x);
else if(op==2) cin>>l>>r>>x,cov(1,1,n,l,r,x);
else if(op==3) cin>>l>>r>>x,add(1,1,n,l,r,x);
else{
cin>>l>>r;
int p=0,s=0;
pil pre=qpre(1,1,n,l,r,p),suf=qsuf(1,1,n,l,r,s);
tmp res=query(1,1,n,l,r);
if(op==4) cout<<pre.fi+suf.fi-res.cnt<<'\n';
else cout<<pre.se+suf.se-1ll*res.mx*(r-l+1)-res.sum<<'\n';
}
}
return 0;
}
```
:::
### [P9130 [USACO23FEB] Hungry Cow P](https://www.luogu.com.cn/problem/P9130)
#### Description
[见题目描述](https://www.luogu.com.cn/problem/P9130)。
#### Solution
使用线段树维护。
由于天数很大,需要动态开点,维护到第 $V=\max d+\sum b=2 \times 10^{14}$ 天。
每个区间维护只考虑当前区间时的信息,$sum$ 表示有干草吃的天数,$ex$ 表示第 $r$ 天之后剩余的干草,$res$ 表示区间有干草吃的时间的编号和。
上传的时候 $ex_{ls}$ 会改变 $sum_{rs}$ 和 $res_{rs}$ 的贡献。
需要实现函数 $f(p,x)$ 计算将线段树上区间 $p$ 初始有 $x$ 堆干草的答案。
显然这 $x$ 堆干草没有全部吃完的时间是一个前缀,可以在线段树上面二分。
需要特判 $x=0$ 和 $p$ 为叶子。
在 $mid$ 天时如果吃完了,那么要求 $sum_{ls}+x \leq len_{ls}$,作差得到右区间贡献,递归左区间计算。
否则没吃完,左区间有贡献 $\sum_{i=l}^{mid}i$,等差数列求和可以直接算出为 $\frac{(l+mid)(mid-l+1)}{2}$,第 $mid+1$ 天有 $x+sum_{ls}+ex_{ls}-len_{ls}$ 堆额外的干草,递归右区间计算。
于是就完成了单侧递归的维护。
时间复杂度 $O(U\log^2 V)$,空间复杂度 $O(U \log V)$。
#### Code
注意答案需要取模。
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=1e5+5,P=1e9+7,I2=(P+1)/2;
const ll V=2e14;
int n;
struct node{
int lson,rson;
ll sum,ex,res;
}t[N<<6];
int rt,cnt;
#define ls (t[p].lson)
#define rs (t[p].rson)
#define mid ((pl+pr)>>1)
#define L ls,pl,mid
#define R rs,mid+1,pr
ll calc(ll l,ll r){
l%=P,r%=P;
return (l+r)*(r-l+1+P)%P*I2%P;
}
ll add(int p,ll pl,ll pr,ll x){
if(!x) return t[p].res;
if(pl==pr) return pl%P;
if(x+t[ls].sum<=mid-pl+1) return (add(L,x)+t[p].res-t[ls].res+P)%P;
return (calc(pl,mid)+add(R,x+t[ls].sum+t[ls].ex-(mid-pl+1)))%P;
}
void up(int p,ll pl,ll pr){
t[p].sum=t[ls].sum+min(t[ls].ex+t[rs].sum,pr-mid);
t[p].ex=t[rs].ex+max(0LL,t[ls].ex+t[rs].sum-(pr-mid));
t[p].res=(t[ls].res+add(rs,mid+1,pr,t[ls].ex))%P;
}
void upd(int &p,ll pl,ll pr,ll x,ll v){
if(!p) p=++cnt;
if(pl==pr){
if(v) t[p].res=pl%P,t[p].sum=1,t[p].ex=v-1;
else t[p].res=0,t[p].sum=0,t[p].ex=0;
return;
}
x<=mid?upd(L,x,v):upd(R,x,v);
up(p,pl,pr);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
while(n--){
ll x,v;
cin>>x>>v;
upd(rt,1,V,x,v);
cout<<t[rt].res<<'\n';
}
return 0;
}
```
:::
### 习题
#### [P13963 [ICPC 2023 Nanjing R] 接雨水](https://www.luogu.com.cn/problem/P13963)
:::info[Hint]
P17826 多测,只有单点修改和全局询问 5。
注意数据范围不同,以及 $mx$ 可能爆 `int`。
:::
#### [P12587 「KTSC 2019 R2」外星仙人掌](https://www.luogu.com.cn/problem/P12587)
:::info[Hint]
P17826 交互式在线,不带修和区间询问 5。
数据范围变成了 $5 \times 10^5$。
:::
#### [P16702 [MCO 2026] 雨水收集](https://www.luogu.com.cn/problem/P16702)
:::info[Hint]
P17826 区间加和区间询问 5。
$n$ 变成了 $5 \times 10^6$,$m$ 变成了 $5 \times 10^4$。
$mx$ 同样可能爆 `int`,同时也可能为负数。
:::
## 复合函数
通常需要维护 $(val,sum)$ 依次经过区间上若干次变换。
每个变换 $f$ 的效果是 $val \gets v_{val},sum \gets sum+ add_{val}$。
$sum$ 的变换可以是只关于 $sum$ 和当前信息的线性变换。
要求 $val$ 值域很小。
### [P15495 [ICPC 2025 APC] Tower of Hanoi](https://www.luogu.com.cn/problem/P15495)
#### Description
[见题目描述](https://www.luogu.com.cn/problem/P15495)。
#### Solution
为了方便,把柱子按照 0-indexed 编号。
考虑 $O(nq)$ 暴力。
反过来,初始 $[l,r]$ 都在 $1$ 上面,要把这些盘子移到 $p_i$ 上。
显然从后往前考虑,记当前 $[l,i]$ 的所有圆盘都在 $pos$ 上。
如果 $p_i=pos$,不操作。
否则把 $[l,i-1]$ 移开,再把 $i$ 移到 $p_i$,进行 $2^{i-l}$ 步操作,$pos \leftarrow 6+pos-p_i$。
$2^{i-l}$ 可以拆成加 $1$ 再在每一个左边的位置进行一次乘 $2$ 操作,或者使用 $2$ 的逆元的幂计算。
需要维护 $(pos,ans)$ 的复合。
如果 $pos=p_i$,$ans \gets 2ans$,即 $v_x=x,add_x=0$。
否则 $pos \gets 3-p_i-pos,ans \gets 2ans+1$,即 $v_x=3-p_i-x,add_x=1$。
每次变换就是 $val \gets v_{val},ans \gets 2ans+ add_{val}$。
考虑区间的合并,由于是从右向左依次变换,需要把右区间代到左区间进行计算。
记左区间的函数为 $(lv,ladd)$,右区间的函数是 $(rv,radd)$。
那么代入得到 $v_x=lv_{rv_x},add_x=ladd_{rv_x}+2^{len_{ls}}radd_{x}$。
区间复合得到的 $add_0$ 就是答案。
时间复杂度 $O(V(n+q\log n))$,空间复杂度 $O(nV)$,其中 $V=3$。
#### Code
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=1e5+5,P=998244353;
int n,q;
int a[N];
int pw[N];
struct node{
int len;
int val[3],add[3];
}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((pl+pr)>>1)
node get(int x){
node res;
res.len=1;
rep(i,0,2) res.val[i]=3-i-x,res.add[i]=1;
res.val[x]=x,res.add[x]=0;
return res;
}
node operator + (const node &l,const node &r){
node res;
res.len=l.len+r.len;
rep(i,0,2) res.val[i]=l.val[r.val[i]],res.add[i]=(l.add[r.val[i]]+1LL*r.add[i]*pw[l.len])%P;
return res;
}
void build(int p,int pl,int pr){
if(pl==pr){
t[p]=get(a[pl]);
return;
}
build(ls,pl,mid);
build(rs,mid+1,pr);
t[p]=t[ls]+t[rs];
}
void upd(int p,int pl,int pr,int x){
if(pl==pr){
t[p]=get(a[pl]);
return;
}
x<=mid?upd(ls,pl,mid,x):upd(rs,mid+1,pr,x);
t[p]=t[ls]+t[rs];
}
node query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return t[p];
if(r<=mid) return query(ls,pl,mid,l,r);
if(l>mid) return query(rs,mid+1,pr,l,r);
return query(ls,pl,mid,l,r)+query(rs,mid+1,pr,l,r);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
rep(i,1,n) cin>>a[i],--a[i];
pw[0]=1;
rep(i,1,n) pw[i]=pw[i-1]*2%P;
build(1,1,n);
while(q--){
char op;
int x,y;
cin>>op>>x>>y;
if(op=='c') a[x]=--y,upd(1,1,n,x);
else cout<<query(1,1,n,x,y).add[0]<<'\n';
}
return 0;
}
```
:::
### [P16541 [EGOI 2026] 饼干 / Biscuits](https://www.luogu.com.cn/problem/P16541)
#### Description
[见题目描述](https://www.luogu.com.cn/problem/P16541)。
#### Solution
考虑 dp 计算每一个后缀。
一个位置能从后面所有的值转移过来。
由于 $ans_A+ans_B=\sum a$,$A$ 最大就要让 $B$ 最小,所以 A 要 ban 掉最大的转移值,只能选次大值,得到一个 $O(nq)$ 暴力。
发现相当于初始两个 $0$,每次给较小的值加上 $a$,求最后较小的那一个值。
容易发现两个值的差不超过 $V$,所以将差值作为 $val$ 维护函数复合即可。
记当前最大和次大值为 $(ma,se)$,$x=ma-se$。
如果 $x \leq w_i$,新的次大值就是原来的最大值,$(ma',se')=(se+w_i,ma)$,$x \gets w_i-x,ans \gets ans+x$。
否则次大值加上 $w_i$,$(ma',se')=(ma,se+w_i)$,$x \gets x-w_i,ans \gets ans+w_i$。
复合 $(lv,ladd)$ 与 $(rv,radd)$ 同样是把右区间代入左区间。
符合得到 $v_x=lv_{rv_x},add_x=ladd_{rv_x}+radd_x$。
时间 $O(V(n+q \log n))$,空间 $O(nV)$,其中 $V=\max W_i=50$。
#### Code
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=1e5+5;
int n,q;
int a[N];
struct node{
int d[51],add[51];
}t[N<<2];
node get(int x){
node res;
rep(i,0,x) res.d[i]=x-i,res.add[i]=i;
rep(i,x+1,50) res.d[i]=i-x,res.add[i]=x;
return res;
}
node merge(node l,node r){
node res;
rep(i,0,50) res.d[i]=l.d[r.d[i]],res.add[i]=r.add[i]+l.add[r.d[i]];
return res;
}
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((pl+pr)>>1)
void build(int p,int pl,int pr){
if(pl==pr){t[p]=get(a[pl]);return;}
build(ls,pl,mid);
build(rs,mid+1,pr);
t[p]=merge(t[ls],t[rs]);
}
void upd(int p,int pl,int pr,int x,int v){
if(pl==pr){t[p]=get(v);return;}
x<=mid?upd(ls,pl,mid,x,v):upd(rs,mid+1,pr,x,v);
t[p]=merge(t[ls],t[rs]);
}
void qry(){
cout<<t[1].add[0]<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
rep(i,1,n) cin>>a[i];
build(1,1,n);
qry();
while(q--){
int p,x;
cin>>p>>x;
upd(1,1,n,++p,x);
qry();
}
return 0;
}
```
:::
### 习题
找不到了。