线段树杂题

· · 算法·理论

历史和/最值

用来做裸题的话不做介绍。

考虑一类问题,给出一个静态序列,多次询问一个区间所有子区间的信息,例如最值 / 数值种类等信息。

可以对区间的一个端点扫描线,例如右端点。

右端点从左往右扫描,使用线段树维护所有左端点到当前右端点的信息。
信息初始化为单点值,然后右端点扫描的时候更新。
再维护每个点的历史信息,例如历史和或历史最值。
这样一个点 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; } ``` ::: ### 习题 找不到了。