无区间最值操作
这里讲两种简易方法：
1.矩阵
考虑线段树的 \(tag\) 必须要有结合律，几个值互相更新，考虑矩阵乘法去实现这个操作。
例题
支持区间加，查询区间和，区间历史版本和。
考虑记一个点的状态为：
$his : $ 区间历史版本和，$sum : $ 区间和，$len : $ 区间长度。
所以区间加 \(c\)，就是左乘上一个矩阵（这个放在右边）
可以手模观察乘出来是什么。
更新一次历史版本就是：
区间覆盖值 \(c\) 就是：
由于矩乘有结合律，所以满足 \(tag\) 的可并性，满足要求。
由于矩乘太慢，我们发现这些矩形都是上三角，记录下来上面的一个三角形就好了，重定义一下乘法和加法。
struct Matrix{
ll a[3];
};
struct Detrix{
ll a[3];
};
Matrix operator +(Matrix x,Matrix y) {x.a[0] += y.a[0]; x.a[1] += y.a[1]; x.a[2] += y.a[2]; return x;}
Matrix operator *(Detrix x,Matrix y)
{
Matrix ret;
ret.a[0] = y.a[0] + y.a[1] * x.a[0] + y.a[2] * x.a[1];
ret.a[1] = y.a[1] + y.a[2] * x.a[2];
ret.a[2] = y.a[2];
return ret;
}
Detrix operator *(Detrix x,Detrix y)
{
Detrix ret;
ret.a[0] = y.a[0] + x.a[0];
ret.a[1] = y.a[1] + y.a[2] * x.a[0] + x.a[1];
ret.a[2] = y.a[2] + x.a[2];
return ret;
}
inline Detrix makeori() {Detrix ret; memset(ret.a,0,sizeof(ret.a)); return ret;}
inline Detrix makeadd(int x) {Detrix ret; ret.a[0] = 0; ret.a[1] = 0; ret.a[2] = x; return ret;}
inline Detrix makecnt() {Detrix ret; ret.a[0] = 1; ret.a[1] = 0; ret.a[2] = 0; return ret;}
struct Segment_Tree{
Matrix a[N << 2];
Detrix tag[N << 2];
inline void pushdown(int pos)
{
if(tag[pos].a[0] == 0 && tag[pos].a[1] == 0 && tag[pos].a[2] == 0) return;
a[pos << 1] = tag[pos] * a[pos << 1];
a[pos << 1 | 1] = tag[pos] * a[pos << 1 | 1];
tag[pos << 1] = tag[pos] * tag[pos << 1];
tag[pos << 1 | 1] = tag[pos] * tag[pos << 1 | 1];
tag[pos] = makeori();
}
inline void pushup(int pos) {a[pos] = a[pos << 1] + a[pos << 1 | 1];}
inline void build(int l,int r,int pos)
{
a[pos].a[2] = r - l + 1;
if(l == r) return;
int mid = (l + r) >> 1;
build(l,mid,pos << 1); build(mid + 1,r,pos << 1 | 1);
pushup(pos);
}
inline void modify(int l,int r,int L,int R,Detrix k,int pos)
{
if(L <= l && r <= R) {
a[pos] = k * a[pos]; tag[pos] = k * tag[pos];
return;
}
int mid = (l + r) >> 1;
pushdown(pos);
if(L <= mid) modify(l,mid,L,R,k,pos << 1);
if(R > mid) modify(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline ll query(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return a[pos].a[0];
int mid = (l + r) >> 1; ll ret = 0;
pushdown(pos);
if(L <= mid) ret += query(l,mid,L,R,pos << 1);
if(R > mid) ret += query(mid + 1,r,L,R,pos << 1 | 1);
pushup(pos);
return ret;
}
}t;
这里没有区间覆盖，所以只记录了三个值，线段树内直接正常操作就好了，十分好理解。
2.辅助数组法
这种方法是在 2016 年吉老师的论文中出现的，极其神仙。
历史和
假设当前的时间为 \(t\) ，记 \(c_i = his_i - t \times a_i\) 。\(his_i\) 是 \(i\) 的历史和，\(a_i\) 是 \(i\) 的值，分两种情况考虑区间加：
-
如果 \(i\) 不在区间内，下一时刻 \(t\) 要加 \(1\) ，\(his_i\) 要加 \(a_i\) ，所以 \(c\) 不变
-
如果在，下一时刻 \(c_i' = (his_i + a_i + k) - (t + 1) \times (a_i + k) = c_i - tk\) 。
所以我们惊奇的发现每次记当前时间，将区间加转化为对 \(a,c\) 的两个区间加，查的时候加起来就行了。
历史最小值
定义辅助数组 \(c_i = a_i - b_i\) ，其中 \(b_i\) 为历史最小值。
分情况，当前值为 \(a_i + k\) ，如果是最小值，\(c_i = 0\) ，如果不是，\(c_i = a_i + k - b_i\) 。所以 \(c_i' = \max(c_i + k,0)\) ，这个区间和 \(-k\) 取 \(max\) 后再加即可，用模板 Segment Tree Beats 解决。
历史最大值
还是 \(c_i = a_i - b_i\) ，如果是最大值， \(c_i = 0\) ，如果不是， \(c_i = a_i + k - b_i\) ，所以 \(c_i' = \min(c_i + k,0)\) ，同理。
下面给出例题求历史和的第二种版本：
struct Segment_Tree{
int abs_t;
ll tagc[N << 2],taga[N << 2],c[N << 2],a[N << 2];
inline void pushdown(int pos,int l,int r)
{
int mid = (l + r) >> 1;
c[pos << 1] += tagc[pos] * (mid - l + 1);
c[pos << 1 | 1] += tagc[pos] * (r - mid);
a[pos << 1] += taga[pos] * (mid - l + 1);
a[pos << 1 | 1] += taga[pos] * (r - mid);
taga[pos << 1] += taga[pos];
taga[pos << 1 | 1] += taga[pos];
tagc[pos << 1] += tagc[pos];
tagc[pos << 1 | 1] += tagc[pos];
tagc[pos] = taga[pos] = 0;
}
inline void pushup(int pos) {c[pos] = c[pos << 1] + c[pos << 1 | 1]; a[pos] = a[pos << 1] + a[pos << 1 | 1];}
inline void modify_a(int l,int r,int L,int R,ll k,int pos)
{
if(L <= l && r <= R) {a[pos] += (r - l + 1) * k; taga[pos] += k; return;}
int mid = (l + r) >> 1;
pushdown(pos,l,r);
if(L <= mid) modify_a(l,mid,L,R,k,pos << 1);
if(R > mid) modify_a(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline void modify_c(int l,int r,int L,int R,ll k,int pos)
{
if(L <= l && r <= R) {c[pos] += (r - l + 1) * k; tagc[pos] += k; return;}
int mid = (l + r) >> 1;
pushdown(pos,l,r);
if(L <= mid) modify_c(l,mid,L,R,k,pos << 1);
if(R > mid) modify_c(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline ll query(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return c[pos] + abs_t * a[pos];
int mid = (l + r) >> 1; ll ret = 0;
pushdown(pos,l,r);
if(L <= mid) ret += query(l,mid,L,R,pos << 1);
if(R > mid) ret += query(mid + 1,r,L,R,pos << 1 | 1);
pushup(pos);
return ret;
}
inline void modify(int l,int r,int L,int R,int x,int pos)
{
modify_a(l,r,L,R,x,1);
modify_c(l,r,L,R,-1ll * abs_t * x,1);
}
}t;
有区间最值操作
上面已经提到，用吉司机的套路转化成区间加解决，代价是 \(\Theta(\log n)\) 的时间和同时维护最值和非最值的信息。
如果是矩阵的话，对于最大值，相应的将 \(len\) 改成最大值个数 \(cnt\) ，对于非最大值，将 $len $ 改为 \(len - cnt\) 。但是由于懒标记在不同时间下传，不同时间的 \(cnt\) 可能不一样，所以不能在某些情况用，现在笔者只清楚它在吉司机操作下的区间和 \(k\) 取最值时是有效的：
- 以区间取最小值为例，考虑懒标记堆叠在一个节点 \(x\) 上，当且仅当 \(max_x > k_1 \geq k_2 \geq \dots \geq k_p > sec_x\) ，所以无论怎么修改，只要 \(k > sec_x\) ，最大值数量都不变。
对于第二种方法，可以转化成区间加，然后相应的改变辅助数组 \(c\) ，从而达到目的，但是这样其实已经十分复杂。
特殊地，对于区间统一赋值操作，可以同样转化成区间加问题，维护最大值，最小值，然后在区间纯色 \(max = min\) 的时候进行区间加，在区间统一赋值的时候这样颜色段均摊的复杂度是正确的。
当然也可以 ODT 维护一下颜色段。