线段树与历史最值问题
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\)），影响到它的操作像是一个队列：
想象逐个处理这些操作的过程。当处理到操作 \(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\) 的时候：
那么我们考虑两个队列的合并，例如将父节点 \(i\) 的标记下放到子节点 \(l\)。
子节点标记：
父节点标记：
接起来：
考虑这个新的队列的前缀和。
考虑这个新的 \(mx_i\)。
即
于是我们就能够处理两个队列合并的情况了。
具体地，对于队列 \(add_l\) 和 \(add_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'))\)。
我们还是和之前一样写出某节点的操作队列。
于是，\(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'))\)。于是每次加入一个新元素的时候，我们令
其中 \(tag=(a,b)\) 意为 \(sum_{op}\) 中最大的 \(a\) 和 \(sum_{op}\) 中最大的 $ b$。
如法炮制，考虑节点 \(i\) 的操作队列 \(op_i\) 下放给儿子 \(l\)（操作队列为 \(op_l\)）。
于是
而这需要我们的 \(\odot\) 操作具有结合律。我们来证明一下其具有结合律。
由定义有，\((a,b)\odot (a',b')=(a+a',\max(b+a',b'))\)
则
而
两者相等。故 \(\odot\) 运算是具有结合律的，可以放心玩弄啦~
证毕。
那么于是 \(tag_l=\max(tag_l,sum_l\odot tag_i)\)。
于是 \(op_i\) 接在 \(op_l\) 后面的时候，我们有
（请仔细思考为什么是这个更新顺序。）
然后就做完了。时间复杂度为 \(\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;
}