线段树与历史最值问题
P4314 CPU 监控
Description
给定数组 \(\{a_i\}\)，维护以下操作。定义一个辅助数组 \(\{b_i\}\)，每次操作完后令 \(b_i=\max(a_i,b_i)\)。
-
查询 \(\max_{i=l}^{r} a_i\)（区间最值）
-
查询 \(\max_{i=l}^{r} b_i\)（历史最值）
-
\(\forall i\in [l,r]\)，\(a_i\gets a_i+v\)（区间修改）
-
\(\forall i\in [l,r]\)，\(a_i\gets v\)（区间覆盖）
Solution
先只考虑修改操作。对于一个节点（最大值 \(v\)，历史最大值 \(h\)），影响到它的操作像是一个队列：
\[add_1,add_2,\cdots,add_k \]想象逐个处理这些操作的过程。当处理到操作 \(i\) 的时候，这个节点的最大值一定会变成 \(v+add_1+add_2+\cdots+add_i\)（我们引入 \(add\) 的前缀和数组 \(sum\)，则改记为 \(v+sum_i\)），但是历史最大值则不然。
为什么历史最大值不一定是 \(v+sum_i\)？因为 \(v+sum_i\) 不一定是出现过的最大值。\(add_i\) 可以为负数，从而 \(sum\) 不具有单调性。但是我们可以想象到，历史最大值一定是 \(\max\left(h,v+\max_{j=1}^{i}sum_j\right)\)。于是我们维护一个 \(mx=\max_{j=1}^{k}sum_j\) 就可以了。
我们当然不可能模拟这个队列，不过现在我们已经可以解决单个值和队列的合并了。当加入一个新的修改操作 \(add\) 的时候：
\[v\gets v+add \]\[sum\gets sum+add \]\[mx\gets \max\left(mx,sum\right) \]\[h\gets\max\left(h,v+mx\right) \]那么我们考虑两个队列的合并，例如将父节点 \(i\) 的标记下放到子节点 \(l\)。
子节点标记：
\[add_{l,1},add_{l,2},\cdots,add_{i,k_l} \]父节点标记：
\[add_{i,1},add_{i,},\cdots,add_{i,k_i} \]接起来：
\[add_{l,1},add_{l,2},\cdots,add_{l,k_l},add_{i,1},add_{i,2},\cdots,add_{i,k_i} \]考虑这个新的队列的前缀和。
\[sum_i\gets \begin{cases} sum_{l,i} & (1\leq i\leq k_l) \\ sum_{l,k}+sum_{i,i-k} & (k_l+1\leq i\leq k_l+k_i) \end{cases} \]考虑这个新的 \(mx_i\)。
\[mx_l\gets \max\begin{cases} \max_{i=1}^{k_l} sum_{l,i} \\ sum_{l,k}+\max_{i=1}^{k_i} sum_{i,i} \end{cases} \]即
\[mx_l\gets \max(mx_l,sum_k+mx_i) \]于是我们就能够处理两个队列合并的情况了。
具体地，对于队列 \(add_l\) 和 \(add_i\) 的合并：
\[v_l\gets sum_l+sum_i \]\[mx_l\gets \max\left(mx_l,sum_l+mx_i\right) \]\[h_l\gets \max(h_l,v_l+mx_i) \]然后我们考虑带赋值操作的情况。将题目中的两种修改看成一种：\((a,b)\)，表示将 \(v\) 改为 \(\max(v+a,b)\)。我们将 \(v=\max(v+a,b)\) 的操作记为 \(v=v\times (a,b)\)。
先考虑两个标记的合并。\(v\) 依次 apply \((a,b)\) 与 \((a',b')\) 后变成了 \(\max\left(\max(v+a,b)+a',b'\right)=\max\left(v+a+a',b+a',b'\right)\)，与 apply 标记 \((a+a',\max(b+a',b'))\) 等效。故 \((a,b)\odot (a',b')=(a+a',\max(b+a',b'))\)。
我们还是和之前一样写出某节点的操作队列。
\[op_1,op_2,\cdots,op_k \]于是，\(k\) 次操作后，我们的 \(v\gets v\times \left(op_1\odot op_2\odot\cdots\odot op_k\right)\)。而历史最大值 \(h\) 更新为 \(\max(h,h+sum_{op}\text{ 中最大的 }a,sum_{op}\text{ 中最大的 } b)\)。
我们不妨定义 \(\max\left((a,b),(a',b')\right)=(\max(a,a'),\max(b,b'))\)。于是每次加入一个新元素的时候，我们令
\[v\gets v\times op \]\[sum\gets sum\odot op \]\[tag\gets \max(tag,sum) \]其中 \(tag=(a,b)\) 意为 \(sum_{op}\) 中最大的 \(a\) 和 \(sum_{op}\) 中最大的 $ b$。
如法炮制，考虑节点 \(i\) 的操作队列 \(op_i\) 下放给儿子 \(l\)（操作队列为 \(op_l\)）。
于是
\[sum_l=\begin{cases} sum_{l,k} & (k\leq k_l) \\ sum_{l,k_l}\odot sum_{i,k-k_l} & (k_l+1\leq k\leq k_l+k_i) \end{cases} \]而这需要我们的 \(\odot\) 操作具有结合律。我们来证明一下其具有结合律。
由定义有，\((a,b)\odot (a',b')=(a+a',\max(b+a',b'))\)
则
\[\begin{aligned} & \left((a_1,b_1)\odot(a_2,b_2)\right)\odot (a_3,b_3)\\ &=(a_1+a_2,\max(b_1+a_2,b_2))\odot (a_3,b_3)\\ &=(a_1+a_2+a_3,\max(\max(b_1+a_2,b_2)+a_3,b_3)) \\ &=(a_1+a_2+a_3,\max(b_1+a_2+a_3,b_2+a_3,b_3)) \end{aligned} \]而
\[\begin{aligned} & (a_1,b_1)\odot\left((a_2,b_2)\odot (a_3,b_3)\right)\\ &=(a_1,b_1)\odot(a_2+a_3,\max(b_2+a_3,b_3))\\ &=(a_1+a_2+a_3,\max(b_1+a_2+a_3,\max(b_2+a_3,b_3))) \\ &=(a_1+a_2+a_3,\max(b_1+a_2+a_3,b_2+a_3,b_3)) \end{aligned} \]两者相等。故 \(\odot\) 运算是具有结合律的，可以放心玩弄啦~
证毕。
那么于是 \(tag_l=\max(tag_l,sum_l\odot tag_i)\)。
于是 \(op_i\) 接在 \(op_l\) 后面的时候，我们有
\[tag_l\gets \max(tag_l,sum_l\odot tag_i) \]\[sum_l\gets sum_l\odot sum_i \]\[h_l\gets \max(h_l,v_l\times tag_i) \]\[v_l\gets v_l\odot sum_i \]（请仔细思考为什么是这个更新顺序。）
然后就做完了。时间复杂度为 \(\mathcal{O}(m\log n)\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MAXN=1e5+10, inf=1ll<<33;
struct tagnode {
int a, b;
tagnode() {
a=0, b=-inf;
}
tagnode(int a, int b): a(a), b(b) {}
void clear() {
*this=tagnode();
}
bool empty() {
return a==0 && b==-inf;
}
tagnode operator*(const tagnode& rhs) const {
return {max(-inf,a+rhs.a),max(b+rhs.a,rhs.b)};
}
tagnode& operator*=(const tagnode& rhs) {
return *this=*this*rhs;
}
friend int operator*(int v, tagnode a) {
return max(v+a.a,a.b);
}
friend int& operator*=(int& v, tagnode a) {
return v=v*a;
}
};
tagnode max(tagnode a, tagnode b) {
return {max(a.a,b.a),max(a.b,b.b)};
}
struct SGT {
#define ll(p) tr[p].l
#define rr(p) tr[p].r
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define val(p) tr[p].val
#define his(p) tr[p].his
#define tag1(p) tr[p].tag1
#define tag2(p) tr[p].tag2
struct node {
int l, r;
int val, his;
tagnode tag1, tag2;
} tr[MAXN<<2];
void pushup(int p) {
val(p)=max(val(ls(p)),val(rs(p)));
his(p)=max(his(ls(p)),his(rs(p)));
}
void pushdown(int p) {
if (tag1(p).empty() && tag2(p).empty()) return;
tag2(ls(p))=max(tag2(ls(p)),tag1(ls(p))*tag2(p));
tag1(ls(p))*=tag1(p);
his(ls(p))=max(his(ls(p)),val(ls(p))*tag2(p));
val(ls(p))*=tag1(p);
tag2(rs(p))=max(tag2(rs(p)),tag1(rs(p))*tag2(p));
tag1(rs(p))*=tag1(p);
his(rs(p))=max(his(rs(p)),val(rs(p))*tag2(p));
val(rs(p))*=tag1(p);
tag1(p).clear(); tag2(p).clear();
}
void build(int l, int r, int a[], int p=1) {
ll(p)=l, rr(p)=r;
tag1(p).clear(); tag2(p).clear();
if (l==r) {
his(p)=val(p)=a[l]; return;
}
int mid=(l+r)>>1;
build(l,mid,a,ls(p)); build(mid+1,r,a,rs(p));
pushup(p);
}
void change(int l, int r, tagnode t, int p=1) {
int cl=ll(p), cr=rr(p);
if (l<=cl && cr<=r) {
tag1(p)*=t;
tag2(p)=max(tag1(p),tag2(p));
val(p)*=t;
his(p)=max(val(p),his(p));
return;
}
int mid=(cl+cr)>>1; pushdown(p);
if (l<=mid) change(l,r,t,ls(p));
if (r>mid) change(l,r,t,rs(p));
pushup(p);
}
int query(int l, int r, int t, int p=1) {
int cl=ll(p), cr=rr(p);
if (l<=cl && cr<=r)
return t?his(p):val(p);
int mid=(cl+cr)>>1, res=-inf; pushdown(p);
if (l<=mid) res=query(l,r,t,ls(p));
if (r>mid) res=max(res,query(l,r,t,rs(p)));
return res;
}
} sg;
int n, m, a[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n;
for (int i=1; i<=n; ++i) cin>>a[i];
sg.build(1,n,a);
cin>>m;
char op; int l, r, v;
while (m--) {
cin>>op>>l>>r;
if (op=='Q') cout<<sg.query(l,r,0)<<'\n';
else if (op=='A') cout<<sg.query(l,r,1)<<'\n';
else if (op=='P') cin>>v, sg.change(l,r,{v,-inf});
else cin>>v, sg.change(l,r,{-inf,v});
}
return 0;
}