P4314 CPU 监控 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，还有一个序列 $h$，初始时 $h=a$，有 $m$ 个操作分四种：

• $\mathrm{qmax}(l,r)$：求 $\underset{i=l}{\overset{r}{\max }}{a}_i$.
• $\mathrm{qhmax}(l,r)$：求 $\underset{i=l}{\overset{r}{\max }}{h}_i$.
• $\mathrm{add}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+k$.
• $\mathrm{assign}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow k$.

每次修改后，对每个 $i\in [1,n]$ 执行 $h_i\leftarrow \max (h_i,a_i)$.

Limitations

$1\le n,m\le 10^5$
$1\le l\le r\le n$
$-2^{31}\le k\le 2^{31}$
$1\text{s},128\text{MB}$

Solution

显然一个区间被 $\mathrm{assign}$ 后，所有 $\mathrm{add}$ 操作都可转化为 $\mathrm{assign}$ 操作.
所以我们要维护：

• $\text{max}$：区间 $a_i$ 最大值.
• $\text{hmax}$：区间 $h_i$ 最大值.
• $\text{add}$：区间 $a_i$ 的 $\mathrm{add}$ 标记.
• $\text{cov}$：区间 $a_i$ 的 $\mathrm{assign}$ 标记.
• $\text{used}$：区间是否被 $\mathrm{assign}$ 过.

然后在 pushdown 时，更新 ${\text{hmax}}^{\prime }=\max (\text{hmax},{\text{max}}^{\prime })$.
但是，如果区间加负数，那么 $\text{hmax}$ 就可能来不及更新，导致错误.
所以节点还需要记录 $\text{add},\text{cov}$ 标记的历史最大值 $\text{hadd},\text{hcov}$，用这两个标记更新 $\text{hmax}$.

接下来打个模板就可以了，时间复杂度 $O(m\log n)$.

Code

$4.75\text{KB},1.26\text{s},7.73\text{MB}\text{(in total, C++20 with O2)}$

// Problem: P4314 CPU 监控
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4314
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}constexpr int inf = 2.1e9;namespace seg_tree {struct Node {int l, r;int max, hismax;int add, hisadd, cov, hiscov;bool used;};inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<int>& a) {const int n = a.size();tr.resize(n << 1);build(0, 0, n - 1, a);}inline void pushup(int u, int mid) {tr[u].max = max(tr[ls(mid)].max, tr[rs(mid)].max);tr[u].hismax = max(tr[ls(mid)].hismax, tr[rs(mid)].hismax);}inline void apply_add(int u, int tag, int histag) {if (tr[u].used) {tr[u].hiscov = max(tr[u].hiscov, tr[u].cov + histag);tr[u].hismax = max(tr[u].hismax, tr[u].max + histag);tr[u].max += tag;tr[u].cov += tag;}else {tr[u].hisadd = max(tr[u].hisadd, tr[u].add + histag);tr[u].hismax = max(tr[u].hismax, tr[u].max + histag);tr[u].max += tag;tr[u].add += tag;}}inline void apply_cover(int u, int tag, int histag) {if (tr[u].used) {tr[u].hiscov = max(tr[u].hiscov, histag);tr[u].hismax = max(tr[u].hismax, histag);}else {tr[u].used = true;tr[u].hiscov = histag;tr[u].hismax = max(tr[u].hismax, histag);}tr[u].max = tr[u].cov = tag;}inline void pushdown(int u, int mid) {apply_add(ls(mid), tr[u].add, tr[u].hisadd);apply_add(rs(mid), tr[u].add, tr[u].hisadd);tr[u].add = tr[u].hisadd = 0;if (tr[u].used) {apply_cover(ls(mid), tr[u].cov, tr[u].hiscov);apply_cover(rs(mid), tr[u].cov, tr[u].hiscov);tr[u].used = false;tr[u].cov = tr[u].hiscov = 0;}}void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].max = tr[u].hismax = a[l];return;}const int mid = (l + r) >> 1;build(ls(mid), l, mid, a);build(rs(mid), mid + 1, r, a);pushup(u, mid);}int qmax(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].max;const int mid = (tr[u].l + tr[u].r) >> 1;int res = -inf;pushdown(u, mid);if (l <= mid) res = max(res, qmax(ls(mid), l, r));if (r > mid) res = max(res, qmax(rs(mid), l, r));return res;}int qhis(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].hismax;const int mid = (tr[u].l + tr[u].r) >> 1;int res = -inf;pushdown(u, mid);if (l <= mid) res = max(res, qhis(ls(mid), l, r));if (r > mid) res = max(res, qhis(rs(mid), l, r));return res;}void add(int u, int l, int r, int v) {if (l <= tr[u].l && tr[u].r <= r) return apply_add(u, v, v);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) add(ls(mid), l, r, v);if (r > mid) add(rs(mid), l, r, v);pushup(u, mid);}void cover(int u, int l, int r, int v) {if (l <= tr[u].l && tr[u].r <= r) return apply_cover(u, v, v);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) cover(ls(mid), l, r, v);if (r > mid) cover(rs(mid), l, r, v);pushup(u, mid);}inline void range_add(int l, int r, int v) { add(0, l, r, v); }inline void range_assign(int l, int r, int v) { cover(0, l, r, v); }inline int range_max(int l, int r) { return qmax(0, l, r); }inline int range_hismax(int l, int r) {return qhis(0, l, r); } };
}
using seg_tree::SegTree;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n; cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) cin >> a[i];int q; cin >> q;SegTree sgt(a);for (int i = 0; i < q; i++) {char op;int l, r, v;cin >> op >> l >> r, l--, r--;if (op == 'Q') cout << sgt.range_max(l, r) << endl;if (op == 'A') cout << sgt.range_hismax(l, r) << endl;if (op == 'P') sgt.range_add(l, r, (cin >> v, v));if (op == 'C') sgt.range_assign(l, r, (cin >> v, v));}return 0;
}