【题解】BZOJ-3064-Tyvj 1518 CPU监控

题目

题意

支持区间加,区间覆盖,区间查询最大值,区间查询历史最大值。

题解

  • 详见吉如一的2016年国家集训队论文《区间最值操作与历史最值问题》。

  • 标记合并有些复杂,而且容易写错。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 1E5 + 100;
const LL inf = 1E10;
LL a[N];

namespace Tree {
#define lson o * 2, l, (l + r) / 2
#define rson o * 2 + 1, (l + r) / 2 + 1, r
struct P { // max(? + x, y)
LL x, y;
} const E = {0, -inf};
P operator / (const P& a, const P& b) {
return {max(-inf, a.x + b.x), max(a.y, a.x + b.y)};
}
P Max(const P& a, const P& b) {
return {max(a.x, b.x), max(a.y, b.y)};
}
struct Node {
P tag, htag;
LL max, hmax;
} t[N << 2];
void up(int o) {
int lc = o * 2, rc = lc + 1;
t[o].max = max(t[lc].max, t[rc].max);
t[o].hmax = max(t[lc].hmax, t[rc].hmax);
}
void do_tag(int o, const Node& x) {
t[o].htag = Max(t[o].htag, x.htag / t[o].tag);
t[o].tag = x.tag / t[o].tag;
t[o].hmax = max(t[o].hmax, max(t[o].max + x.htag.x, x.htag.y));
t[o].max = max(t[o].max + x.tag.x, x.tag.y);
}
void build(int o, int l, int r) {
t[o].tag = t[o].htag = E;
if (l == r) t[o].max = t[o].hmax = a[l];
else { build(lson); build(rson); up(o); }
}
void down(int o) {
do_tag(o * 2, t[o]); do_tag(o * 2 + 1, t[o]);
t[o].tag = t[o].htag = E;
}
void update(int ql, int qr, const P& x, int o, int l, int r) {
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) { do_tag(o, {x, E, -1, -1}); return; }
down(o);
update(ql, qr, x, lson); update(ql, qr, x, rson);
up(o);
}
LL query(int ql, int qr, int type, int o, int l, int r) {
if (r < ql || qr < l) return -inf;
if (ql <= l && r <= qr) return type ? t[o].hmax : t[o].max;
down(o);
return max(query(ql, qr, type, lson), query(ql, qr, type, rson));
}
}
using namespace Tree;


char s[10];
int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int n; cin >> n;
FOR (i, 1, n + 1) scanf("%lld", &a[i]);
build(1, 1, n);
int Qn; cin >> Qn;
while (Qn--) {
int l, r;
scanf("%s%d%d", s, &l, &r);
if (s[0] == 'Q') printf("%lld\n", query(l, r, 0, 1, 1, n));
else if (s[0] == 'A') printf("%lld\n", query(l, r, 1, 1, 1, n));
else {
int x; scanf("%d", &x);
if (s[0] == 'P') update(l, r, {x, -inf}, 1, 1, n);
else if (s[0] == 'C') update(l, r, {-inf, x}, 1, 1, n);
}
}
}