线段树进阶（势能分析，segbeats，历史值标记）

· · 个人记录

例题 1：#228. 基础数据结构练习题

考虑区间开方之后极差的变化。根据 x^2-y^2=(x+y)(x-y)\geq (x-y)^2 得到极差至少也会开方（由于下取整的原因常数上会有一点偏差不过不影响复杂度）。所以一个极差为 a 的区间开方 \log\log a 次以后极差就会变为 0 或 1。

若区间的极差在开方之后不变（极差为 0，或者极差为 1 并且最大值 x 是完全平方数），那么区间开方相当于区间减一个数，打加法标记即可。区间加操作同样打加法标记即可。

若区间的极差在开方之后变化，那么递归修改两个子区间，然后这个区间的极差至少会开方。

用线段树维护，维护的信息有区间和、区间最大值、区间最小值，标记有区间加标记。修改操作只会导致涉及到的 \log n 个区间的极差增加。时间复杂度即为 O((n+m\log n)\log\log a)。

例题 2：HDU5306 Gorgeous Sequence

题意：区间和 x 取 \min，求区间最大值和区间和。

这种区间取 \min/\max 的题目使用的线段树一般被称为 segment tree beats。

维护区间最大值 mx，严格次大值 mx2，最大值出现次数 c，区间和 s，区间取 \min 标记 t。

考虑让当前区间和 x 取 \min。若 x\geq mx，则什么都不用做。若 mx>x>mx2，则只需要将区间内所有 c 个值为 mx 的数都改成 x，更新 s\leftarrow s-(mx-x)c,mx\leftarrow x,t\leftarrow x。若 x\leq mx2，则暴力递归修改两个子区间。下传标记时分别判断两个子区间的 mx 是否大于当前区间的 t，若是则将 mx 改为 t，更新 s，并继续打标记。

分析一下这样做的时间复杂度。初始时线段树上所有区间的数的种类数之和是 n\log n 级别。考虑递归时经过一个 x\leq mx2 的区间，一定会将值为 mx 和 mx2 的数都改为 x，导致区间的数的种类数至少减 1。再加上区间操作本身的复杂度 m\log n，时间复杂度即为 O((n+m)\log n)。

例题 3：#4695. 最假女选手

不考虑区间加操作，和上一题差不多，多维护最小值、次小值、最小值出现次数、取 \max 标记即可。注意取 \max 的时候可能会影响最大值和次大值，不过不会影响出现次数（因为和 v 取 \max 时一定有 mn<v<mn2）。

考虑区间加操作，增加一个区间加标记，优先级高于取 \max 取 \min 标记，下传区间加标记的时候，更新另外两个标记、区间和、和所有区间最值信息。

实现时有一个 trick，就是不需要记录取 \max 取 \min 标记，直接将当前结点的最大值当做取 \min 标记下传给儿子结点即可。

分析复杂度。

区间加操作最坏情况可能让一个区间内数的种类数翻倍，所以上一题的证明不管用了。

对于线段树上的结点 x，若 x 的区间最大值和 fa_x 的区间最大值不同，则将 x 视为关键点。初始时关键点的数量是 n 级别，一次区间修改操作只会增加 \log n 级别个关键点。

考虑区间取最小值操作暴力递归的过程。假设要和 v 取最小值。对于一个结点 x，若 mx2_x<v，则不会继续递归 x 的儿子，称 x 为终止结点。考虑所有的结点 fa，满足其两个儿子 x,y 都是终止结点。如果 mx_x,mx_y 都和 mx_{fa} 相等，则 x,y 中存在 mx2_{fa} 的区间会继续向下递归，和终止结点的条件矛盾。不妨设 mx_x<mx_{fa}，则一定有 mx_x=mx2_{fa}，否则 y 就不是终止结点。所以修改之前 x 是关键点，修改后 x 不是关键点。设递归的过程经过了 k 个 x 这样的点，则递归时只可能经过所有 x 到根路径上包含的点，以及这些点的儿子，点数为 k\log n 级别。所以可以以 \log n 的代价让关键点数量减少 1，所以时间复杂度是 O((n+m\log n)\log n)。考虑区间取最大值和最小值，容易发现两部分没有影响，复杂度不变。

只要操作满足区间内值相同的数操作后值仍然相同，那么“一次区间修改操作只会增加 \log n 级别个关键点”就成立，所以可以将区间加换成其他操作（比如区间乘），用同样的做法复杂度不变。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int u,v,w,mn,mx;
ll sm;
struct T{ll s;int i,i2,ic,a,a2,ac,t,l;}s[1048579];
//s表示区间和，i表示最小值，i2表示次小值，ic表示最小值出现次数，t表示区间加标记，l表示区间长度
#define _ s[k],s[k*2],s[k*2+1]
#define I int k,int l,int r
#define M int m=(l+r)>>1;
#define L k*2,l,m
#define R k*2+1,m+1,r
#define W(F) M if(dn(_),u<=m)F(L);if(m<v)F(R);up(_);
auto ad=[](T&k,int v){k.i+=v,k.i2+=v,k.a+=v,k.a2+=v,k.t+=v,k.s+=k.l*1ll*v;};//k对应区间加v
auto cmn=[](T&k,int v){//k对应区间和v取min，保证k.a2<v<k.a
    if(k.i2==k.a)k.i2=v;else if(k.i==k.a)k.i=v;
    k.s+=(v-k.a)*1ll*k.ac,k.a=v;
};
auto cmx=[](T&k,int v){//取max
    if(k.a2==k.i)k.a2=v;else if(k.a==k.i)k.a=v;
    k.s+=(v-k.i)*1ll*k.ic,k.i=v;
};
auto dn=[](T&k,T&a,T&b){//下传三种标记
    if(k.t)ad(a,k.t),ad(b,k.t),k.t=0;
    if(k.a<a.a)cmn(a,k.a);if(k.a<b.a)cmn(b,k.a);
    if(k.i>a.i)cmx(a,k.i);if(k.i>b.i)cmx(b,k.i);
};
auto up=[](T&k,T&a,T&b){//上传信息
    if(k.s=a.s+b.s,a.a>b.a)k.a=a.a,k.ac=a.ac,k.a2=max(a.a2,b.a);
    else if(a.a<b.a)k.a=b.a,k.ac=b.ac,k.a2=max(a.a,b.a2);else k.a=a.a,k.ac=a.ac+b.ac,k.a2=max(a.a2,b.a2);
    if(a.i<b.i)k.i=a.i,k.ic=a.ic,k.i2=min(a.i2,b.i);
    else if(a.i>b.i)k.i=b.i,k.ic=b.ic,k.i2=min(a.i,b.i2);else k.i=a.i,k.ic=a.ic+b.ic,k.i2=min(a.i2,b.i2);
};
void bd(I){//建树
    if(s[k].l=r-l+1,l==r){cin>>w,s[k].s=s[k].i=s[k].a=w,s[k].a2=-(s[k].i2=1e9),s[k].ac=s[k].ic=1;return;}
    M bd(L),bd(R),up(_);
}
void add(I){if(u<=l&&r<=v)return ad(s[k],w);W(add)}//区间加
void umx(I){//区间取max
    if(s[k].i>=w)return;
    if(u<=l&&r<=v&&s[k].i2>w)return cmx(s[k],w);W(umx)
}
void umn(I){//区间取min
    if(s[k].a<=w)return;
    if(u<=l&&r<=v&&s[k].a2<w)return cmn(s[k],w);W(umn)
}
void qry(I){//区间查询
    if(u<=l&&r<=v){sm+=s[k].s,mn=min(mn,s[k].i),mx=max(mx,s[k].a);return;}
    M if(dn(_),u<=m)qry(L);if(m<v)qry(R);
}
int main(){ios::sync_with_stdio(0),cin.tie(0);
    int n,m,i;
    for(cin>>n,bd(1,1,n),cin>>m;m--;)if(cin>>i>>u>>v,i==1)cin>>w,add(1,1,n);
    else if(i==2)cin>>w,umx(1,1,n);else if(i==3)cin>>w,umn(1,1,n);
    else mn=1e9,mx=-1e9,sm=0,qry(1,1,n),cout<<(i==4?sm:(i==5?mx:mn))<<'\n';
}

例题 4：CF855F Nagini

对正负数分别考虑，转化为区间取 \min 和区间求和，用例题 2 的做法即可。

假设初始值为 inf，这题多一个限制，就是只有一个位置正负都小于 inf 才能计入答案。容易发现一个数正负分别只会从 inf 变为小于 inf 的数一次。区间和 x 取 \min 时，若 mx2<x<mx，并且 mx=inf，则暴力重构 x 的子树的信息，每个位置正负分别只会重构一次，这部分就是 O(n\log n)。总复杂度 O((n+m)\log n)。

例题 5：CF793F Julia the snail

将询问按 y 从小到大排序，维护所有 x 的答案。需要支持单点查询，将下标 \leq l 且值 \geq l 的数改成 r。考虑线段树，维护区间最大值 mx，次大值 mx2。若 mx<l，则没有数会被修改，直接 return。若 mx2<l\leq mx，则将值为 mx 的数改成 r。若 l\leq mx2，继续递归儿子。

考虑 pushdown 如何实现，假设父亲结点为 fa，儿子为 x,y。求出 w=\max(mx_x,mx_y)。若 w=mx_{fa}，则什么都不用做。否则将 mx_x,mx_y 中和 w 相等的数改成 mx_{fa}。

复杂度证明和例题 2 一样，为 O((n+m+q)\log n)。

例题 6：CF1290E Cartesian Tree

考虑从小到大加数，l_i 表示当前子序列中，i 左边第一个比 a_i 大的位置。比如，假设 a=\{2,5,4,3,1\}，只加入 \leq 4 的数，i=4，a_i=3，当前子序列是 {2,4,3,1}，左边第一个比 3 大的位置就是 2（值为 4），所以 l_4=2。同理定义 r_i 为右边第一个比 a_i 大的位置。容易发现，i 的子树大小就是 r_i-l_i-1。考虑新加入 a_p=x，那么 r_p=x+1。对于 i\in[p+1,n],a_i<x，r_i=r'_i+1。对于 i\in[1,p-1],a_i<x，r_i=\min(r'_i,p')，其中 p' 为 x 在子序列中的位置。需要支持区间加，区间取 \min，单点修改，求全局和，用例题 3 的做法即可。记 p 满足 p_{a_i}=i。求出 r 之后将 p_i 改为 n+1-p_i，再求一遍，求出的即为 x+1-l_i，将两次的结果的前缀和加起来记为 res_i，res_i-i(i+2) 即为答案。时间复杂度 O(n\log^2 n)。

例题 7：

P4314 CPU 监控

区间加，区间赋值，求区间最大值，求区间历史最大值的最大值。

对于原数列 a 和一个新数列 b，初始 b=a，每次操作后都令 b_i\leftarrow \max(b_i,a_i)，b_i 即为位置 i 的历史最大值。

考虑只有区间加。维护当前加法标记 a0 和加法标记的历史最大值 a1，维护区间当前最大值 w0 和历史最大值 w1。考虑 pushdown 的过程。假设当前要将 fa 的标记下传到 x。那么 a0_x\leftarrow a0_x+a0_{fa},w0_x\leftarrow w0_x+a0_{fa}。关键是 a1,w1 如何更新。容易发现，a1_x=\max(a1_x,a0_x+a1_{fa}),w1_x=\max(w1_x,w0_x+a1_{fa})，注意这里的 w0,a0 是修改前的。下传结束后，重置 a0_{fa}=a1_{fa}=0。

考虑加上赋值操作。容易发现，如果存在赋值标记，那么区间的所有数都会变得相同，之后的加法操作也可以视为赋值。于是 pushdown 可以转化为先加再赋值，或者只有加没有赋值。维护当前赋值标记 c0 和赋值标记的历史最大值 c1，再维护一个 bool 类型 b 表示是否有赋值操作。若 b_{fa}=1，则需要下传赋值标记，然后重置 b_{fa}=0。下传时，若 b_x=1，则 c1_x\leftarrow \max(c1_x,c1_{fa})，否则 b_x\leftarrow 1,c1_x\leftarrow c1_{fa}。c0_x\leftarrow c0_{fa},w0_x\leftarrow c0_{fa},w1_x\leftarrow \max(w1_x,c1_{fa})。下传加法标记的过程也有不同，若 b_x=1，则不修改 a0_x,a1_x，改为用同样的方式修改 c0_x,c1_x。

pushup 很简单，w0,w1 分别改为子区间的 w0,w1 的最大值即可。

时间复杂度 O(n+q\log n)。

#include<bits/stdc++.h>
using namespace std;
#define L k*2,l,m
#define R k*2+1,m+1,r
#define M int m=(l+r)>>1;
#define _ s[k],s[k*2],s[k*2+1]
#define I int k,int l,int r
#define W(F) M if(dn(_),u<=m)F(L);if(m<v)F(R);
int a[100009],u,v,w,w1;
struct T{int a,a1,c,c1,w,w1;bool b;}s[262199];
auto ad=[](T&k,int t,int t1){if(k.w1=max(k.w1,k.w+t1),k.w+=t,k.b)k.c1=max(k.c1,k.c+t1),k.c+=t;else k.a1=max(k.a1,k.a+t1),k.a+=t;};//下传加法标记
auto cv=[](T&k,int t,int t1){if(k.c=k.w=t,k.w1=max(k.w1,t1),k.b)k.c1=max(k.c1,t1);else k.b=1,k.c1=t1;};//下传赋值标记
auto dn=[](T&k,T&a,T&b){if(ad(a,k.a,k.a1),ad(b,k.a,k.a1),k.a=k.a1=0,k.b)cv(a,k.c,k.c1),cv(b,k.c,k.c1),k.b=0;};//pushdown
auto up=[](T&k,T&a,T&b){k.w=max(a.w,b.w),k.w1=max(a.w1,b.w1);};//pushup
void bd(I){if(l==r){s[k].w=s[k].w1=a[l];return;}M bd(L),bd(R),up(_);}//建树
void add(I){if(u<=l&&r<=v)return ad(s[k],w,w);W(add) up(_);}//区间加
void cov(I){if(u<=l&&r<=v)return cv(s[k],w,w);W(cov) up(_);}//区间赋值
void qry(I){if(u<=l&&r<=v){w=max(w,s[k].w),w1=max(w1,s[k].w1);return;}W(qry);}//区间最大值和历史最大值
int main(){ios::sync_with_stdio(0);cin.tie(0);
    int n,q,i;char c;
    for(cin>>n,i=1;i<=n;++i)cin>>a[i];
    for(bd(1,1,n),cin>>q;q--;)if(cin>>c>>u>>v,c=='Q'||c=='A')w=w1=INT_MIN,qry(1,1,n),cout<<(c=='Q'?w:w1)<<'\n';else if(cin>>w,c=='P')add(1,1,n);else cov(1,1,n);
}

例题 8：

SP1557 GSS2 - Can you answer these queries II

如何处理相同的数只算一次的条件？考虑用类似 P1972 [SDOI2009]HH的项链 的做法。将询问离线按右端点从小到大排序，从左到右依次加入序列中的元素。设当前加入 a_r，记 a_i 上一次出现的位置是 b_i（不存在为 0），对位置 i，维护去重后的后缀和 s_i=\sum_{i\leq j\leq r}[b_j<i]a_j，容易发现区间 [i,r] 的答案即为 j\in[i,r] 的 s_j 的历史最大值的最大值。考虑加入 a_r 的影响，相当于对 [b_r+1,r] 的 s_j 区间加 a_r。需要支持区间加和区间历史最大值，做法同例题 7，O((n+q)\log n)。

例题 9：CF997E Good Subsegments

弱化版：CF526F Pudding Monsters 题意转化为有一个长为 n 的排列，求 w=max-min-len=-1 的子区间个数。考虑从小到大枚举右端点 r，维护 r 个后缀的 w 的值。max,min 可以用单调栈维护，len 直接对 [1,r] 减一即可。需要支持区间加，求等于 -1 的值个数，容易发现 -1 一定是最小值，所以改为维护最小值的个数，线段树即可，O(n\log n)。

再考虑一个弱化版，询问区间 [l,r] 的所有后缀，有多少个是好的。右端点扫到 r 的时候区间 [l,r] 的最小值个数即为答案。

考虑此题。若区间 [l,r] 的某一个位置在某时刻是最小值，则对答案有 1 的贡献。于是要求一个类似区间历史版本和的和的东西。考虑增加一个历史值标记 h，和历史版本和 w。w 表示区间内每个位置是最小值的时刻数的和，h 表示对子区间中等于当前区间最小值的位置的时刻数增加 h。pushdown 时，先下传区间加标记，然后下传 h 标记（如果子区间的最小值大于当前区间的最小值则不下传），记 c 为区间最小值出现次数，将 fa 的标记下传到 x 时，h_x\leftarrow h_x+h_{fa},w_x\leftarrow w_x+c_x h_{fa}。每扫过一个右端点，就对根结点的 h 加一。h,w 只会自顶向下更新，所以不需要在 pushup 的时候更新。O((n+q)\log n)。

例题 10：G. Prof. Pang's sequence

从小到大枚举右端点，记 b_i 为 a_i 上一次出现的位置，不存在为 0。维护当前每个后缀出现数的种类的奇偶性，相当于对 [b_i+1,i] 区间取反，求区间历史版本和的和。但是这个题和上一题有一些区别，就是上一题维护的是最小值个数，对一个区间加一个数不会影响当前区间内部的最小值个数。但是这个题维护的是区间和，区间取反会影响区间内部的和。容易发现，对一个区间多次取反只有两种状态，也就是取反和不取反。维护两个历史值标记 h0,h1，h0 表示不取反需要计入贡献 h0 次，h1 表示取反。用这两个标记和当前的区间和 s 更新历史版本和 w 即可。O((n+m)\log n)。

用类似的做法也可以解决区间加，区间历史版本和，h 表示所有加法标记的和即可。

例题 11：P6242 【模板】线段树 3

三倍经验：#169. 【UR #11】元旦老人与数列 #170. Picks loves segment tree VIII

修改：区间加，区间取 \min

查询：区间和，区间最大值，区间历史最大值的最大值

例题 3 + 例题 7。

考虑例题 3 的做法，需要维护最大值和次大值，以及取 \min 和加法两种标记。然而取 \min 标记并没有像例题 7 的赋值标记那样良好的性质，将两种标记合并之后就会出现加法、取 \min、加法这样两种标记交替的情况，一个结点的标记的总数会达到 O(m) 级别。

容易发现一个性质，就是和 v 取 \min 一定满足 mx2<v<mx，所以相当于将区间内等于 mx 的数减 mx-v。考虑维护两种加法标记 t 和 tmx，tmx 表示将区间内最大值加 tmx，t 表示将区间内除了最大值以外的数加 t。pushdown 的时候，求出 w 表示两个子区间的最大值，对等于 w 的数增加 tmx，对小于 w 的数增加 t 即可。

现在只有加法这一种标记了，就可以沿用例题 7 的做法，增加两个历史值标记 t1,tmx1 分别表示 t,tmx 的历史最大值。于是每个结点需要维护以下信息：最大值 mx，次大值 mx2，历史最大值 mx1，四个标记 t,tmx,t1,tmx1，最大值出现次数 c，区间和 s。时间复杂度 O((n+m\log n)\log n)。

uoj 170 还要稍微复杂一些。考虑维护三种加法标记 t,tmx,tmn 以及对应的两种历史值标记（历史最大和历史最小）。一些细节：需要注意当区间内只有一种或两种数时，tmx 可能会影响最小值 mn 和次小值 mn2，同理 tmn 也可能影响最大值和次大值。对于和 v 取 \min 操作，在 mx2<v<mx 时，转化为等于 mx 的数加 v-mx，将 mx 修改完之后，若 mx<mn，意味着区间内只有一种数，对 mn 也进行修改并打上标记，取 \max 操作同理。在对 mx 加 v 的时候，若 mx=mn2，意味着区间内只有两种数，对 mn2 也加 v（但不影响 tmn 和 t）。pushdown 的时候需要考虑三种情况，假设两个子区间分别为 x,y，求出 mx0=\max(mx_x,mx_y),mn0=\min(mn_x,mn_y)，若 mx0=mx_x，则用 tmx 更新 mx_x；若 mn0=mx_x 则用 tmn 更新；否则用 t 更新。

总结：对于一类需要支持区间取 \min 的问题，可以考虑维护最大值 mx 和次大值 mn，然后将操作转化为对等于 mx 的数和小于 mx 的数分别区间加，用两套加法标记解决。

uoj 170 代码：

#include<bits/stdc++.h>
using namespace std;
#define S s[k]
#define _ s[k*2],s[k*2+1]
#define F(o) o<mx?(o>mn?t:ti):ta
const int I=2e9+9;//inf
int n,m,o,u,v,w;
struct L{//存标记的结构体
    int t,a,i;//t是加法标记，a是t的历史max，i是历史min
    L(int v=0):t(v),a(v),i(v){}
    void operator+=(const L&x){a=max(a,t+x.a),i=min(i,t+x.i),t+=x.t;}//标记合并
};
struct T{
    L t,ta,ti;int a,a2,ah,i,i2,ih;//ta是最大值标记，ti是最小值标记，t是其他值标记，a是最大值，a2是次大值，ah是历史最大值，i是最小值，i、i2同理
    void ada(const L&x){i2==a?i2+=x.t:0,ah=max(ah,a+x.a),ta+=x,a+=x.t;}//最大值加上标记x，注意次小值等于最大值的情况
    void adi(const L&x){a2==i?a2+=x.t:0,ih=min(ih,i+x.i),ti+=x,i+=x.t;}//最小值加上标记x
    void ad(const L&x){if(i2<=a2)i2+=x.t,a2+=x.t,t+=x;}//其他值加上标记x，如果没有其他值就什么都不做，防止inf加上x.t以后爆int
    void dn(T&x,T&y){//下传标记
        int mn=min(x.i,y.i),mx=max(x.a,y.a);
        x.ada(F(x.a)),y.ada(F(y.a)),x.adi(F(x.i)),y.adi(F(y.i)),x.ad(t),y.ad(t),t=ta=ti=0;//下传时分三种情况讨论，等于mn，等于mx，都不等于
    }
    void up(T&x,T&y){//上传信息
        ih=min(x.ih,y.ih),i=min(x.i,y.i),i2=min(i<x.i?x.i:x.i2,i<y.i?y.i:y.i2);
        ah=max(x.ah,y.ah),a=max(x.a,y.a),a2=max(a>x.a?x.a:x.a2,a>y.a?y.a:y.a2);
    }
}s[1048599];
void umx(int k){if(S.i<w)S.i2>w?(S.i<S.a?void():S.ada(w-S.i),S.adi(w-S.i)):(S.dn(_),umx(k*2),umx(k*2+1),S.up(_));}//区间取max，次小值大于w时修改区间最小值，注意区间内只有一种值的时候需要将区间最大值也修改
void umn(int k){if(S.a>w)S.a2<w?(S.i<S.a?void():S.adi(w-S.a),S.ada(w-S.a)):(S.dn(_),umn(k*2),umn(k*2+1),S.up(_));}//区间取min
void bd(int k,int l,int r){//建树
    if(l==r)cin>>w,S.a=S.ah=S.i=S.ih=w,S.a2=-I,S.i2=I;
    else{int m=(l+r)>>1;bd(k*2,l,m),bd(k*2+1,m+1,r),S.up(_);}
}
void wk(int k,int l,int r){//处理所有操作
    if(u<=l&&r<=v)o<2?(S.ada(w),S.adi(w),S.ad(w)):(o<3?umx(k):(o==5?umn(k):(o<5?w=min(w,o<4?S.i:S.ih):w=max(w,S.ah),void())));
    else{int m=(l+r)>>1;if(S.dn(_),u<=m)wk(k*2,l,m);if(m<v)wk(k*2+1,m+1,r);S.up(_);}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);
    for(cin>>n>>m,bd(1,1,n);m--;){
        if(cin>>o>>u>>v,o<3||o==5)cin>>w;else if(o<5)w=I;else w=-I;
        if(wk(1,1,n),o>2&&o!=5)cout<<w<<'\n';
    }
}

例题 12：Picks loves segment tree VI

维护 k 个数列，需要支持对某一个数列区间加、区间取 \max，查询区间内 a_{1,i}+a_{2,i}+\cdots+a_{k,i} 的最值。

考虑维护 2^k 套标记。以 k=2 的情况为例，维护四套加法标记，分别表示 a_1,a_2 都是最小值，a_1 是最小值但 a_2 不是，a_2 是 a_1 不是，a_1,a_2 都不是。

再维护 a_1,a_2\cdots a_k 的最小值次小值。

对每套标记，维护对应的 a_{1,i}+a_{2,i}+\cdots+a_{k,i} 的最值。区间加操作，相当于给每一套标记都区间加。区间取 \max 操作，相当于只给对应数列是最小值的标记区间加。

pushup 的时候好像需要高维前缀和，处理子区间最小值不等于当前区间最小值的情况，复杂度是 O(k2^k(n+m\log n)\log n)。

例题 13：#515. 【UR #19】前进四

可以直接用线段树维护区间单调栈（楼房重建） ，复杂度 O(n\log^2 n)，不能通过。

考虑此题的性质，就是右端点一定是 n，并且可以离线。从大到小枚举下标 x，按时间建线段树，线段树上每个位置 i 维护时间 i 时 [x,n] 的最小值。对于修改操作，求出其影响的时间段 [l,r]，相当于区间 [l,r] 和 v 取 \min。对于时间 i 的查询操作，相当于求位置 i 被取 \min 了多少次。维护最大值、次大值、最大值被取 \min 的次数标记 s 即可，pushdown 的时候将 s 下传给最大值等于当前区间最大值的子区间。

例题 14：#671. 【UNR #5】诡异操作

考虑没有区间与操作怎么做。显然一个数只会被除 \log v 次（将除 1 的操作排除掉）。用线段树维护区间和模 2^{128} 的值，以及区间内是否存在非零数。若存在非零数，则继续向下递归，直到递归到叶子。分析复杂度，考虑在线段树上锁定询问区间以后的搜索过程（即当前区间 [l,r] 被询问区间 [u,v] 包含），每个区间只会被搜索到 \log v 次，总复杂度即为 O(n\log v+q\log n)。

考虑加上区间与操作。对与操作打标记。对每个结点开一个长度为 \log v 的数组表示每一位区间内有多少个 1，这样就可以求区间和以及判断是否存在非零数。容易发现与操作不会影响只除 \log v 次的性质。所有操作的复杂度都乘上一个 \log v，即为 O(n\log^2 v+q\log n\log v)，不能通过。

考虑优化。容易发现递归到线段树深层结点的时候，数组中的数都非常小，不超过区间长度 len，用 int 存很浪费。考虑压位，用 \log len 个 __int128，第 i 个数 p_i 的第 j 位表示原本长度为 \log v 的数组中，第 j 个数的第 i 位（下标从 0 开始）。单点除 v，直接将 p_0 除 v 即可。区间与 v，相当于对这 \log len 个数与 v。求区间和，第 i 个数 x 对答案的贡献是 2^ix。pushup 的时候，模拟二进制加法的进位过程即可。这些操作的复杂度都变成 \log len。锁定区间部分的复杂度变为 O(q\log^2 n)。考虑分析除法部分的复杂度，也就是 \log v\sum \log len，其中 \sum \log len 容易得到是 n 级别的。总复杂度即为 O(n\log v+q\log^2 n)。

例题 15：#164. 【清华集训2015】V

直接套 seg-beats 是两个 \log 比较慢。

可以将所有修改操作转化为先加 x 再对 y 取 \max。

考虑对区间打标记 (x,y) 表示先加 x 再对 y 取 \max。考虑合并两个标记 (x,y),(p,q)，容易发现是 (x+p,\max(y+p,q))。

考虑历史值询问，再加一对历史值标记 (x1,y1) 即可，容易发现两个标记取 \max 就是对 x,y 分别取 \max，所以有 x1\leftarrow \max(x1,x+p1),y1\leftarrow \max(y1,\max(y+p1,q1))。

考虑下传标记，将子区间的标记与 (x,y),(x1,y1) 合并，然后 x,y,x1,y1 全部清零即可。复杂度 O(n+m\log n)。

例题 16：P6109 [Ynoi2009] rprmq1

考虑将修改差分，变为 (l_1,l_2,r_2,x),(r_1+1,l_2,r_2,-x)。

从小到大枚举 i 这一维，对 j 这一维开线段树，修改转化为区间加。若查询满足 l_1=r_1，直接在加入 \leq r_1 的修改以后查询 [l_2,r_2] 的最大值即可。若查询满足 l_1=1，则查询历史最大值即可。

考虑“猫树分治”，也就是两区间合并。其实本题并没有进行区间的合并，只是用到了猫树的分治结构。将查询的 [l_1,r_1] 放到猫树上，若 l_1<r_1 则一定会被拆成恰好两个区间。将猫树上的结点区间的左右端点作为关键点，则拆成的两个区间一个是以关键点为右端点，另一个是以关键点为左端点，对这两类分别处理即可。以关键点是左端点的情况为例，显然不能对每个结点开线段树，考虑按层处理，从小到大枚举 i 这一维，到达一个左端点关键点的时候要将之前的历史最大值清掉，一种巧妙的做法是在线段树上全局加 inf，查询的时候再减掉，inf 不能取得太大，不然 inf\times n 会爆 long long。复杂度 O(m\log^2 n+(n+q)\log n)。