Luogu P4314 CPU监控

[模板] 线段树3

我真的佛了,标记下传神题

第一眼就秒出思路,维护一个max和一个历史最大值hmax,维护加法add,维护改变set。

然而这样是布星的。想一种情况,你有一个add,如果下传下去下面的max就会成为新的hmax,但有个set截了胡,把这个add覆盖掉了,那这个add还没更新答案就挂掉了,答案就错了。

我们的问题既然是出现在了这里,我们就再维护一个截至到上次pushdown的最大add hadd和最大set hset。

然后就是喜闻乐见的pushdown函数的设计了

首先有一个思路,就是先用父节点传下来的h-信息更新了子节点的h-信息,再更新子节点的普通信息。

pushdown这部分的思路写在了代码注释里。

还是说个坑点:建树和pushdown结束后记得给(h)set赋个初值。由于有可能出现负数,你这初值得是负的,-INF。

再说下我自己的Sb错误:query_history是直接copy的query_now,change是直接copy的add,导致我不断在change里调用add。。。。复制粘贴需谨慎。。。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>

const int N = 1000000 + 2333, INF = 0x3f3f3f3f;
int n, m, a[N];
struct SegTree {
int l, r, add, hadd, set, hset, mx, hmx;
} t[N << 2];

void pushup(int p) {
t[p].mx = std::max(t[p << 1].mx, t[p << 1 | 1].mx);
t[p].hmx = std::max(t[p << 1].hmx, t[p << 1 | 1].hmx);
}

void pushdown(int p) {
//迫真for循环减少码量
for (int i = (p << 1); i <= (p << 1 | 1); i++) {
//先把几个历史最大值维护了
t[i].hmx = std::max(
t[i].hmx,
std::max(t[p].hset, t[p].hadd + t[i].mx)); //用his信息先更新hmax
if (t[i].set != -INF)
t[i].hset = std::max(
t[i].hset, t[i].set + t[p].hadd); //下放掉hadd,儿子有set就更新了hset
else
t[i].hadd = std::max(t[i].hadd, t[p].hadd + t[i].add); //否则更新hadd
t[i].hset = std::max(t[i].hset, t[p].hset); //下放hset
if (t[p].add) { //下放add
if (t[i].set != -INF)
t[i].set += t[p].add; //有set直接叠加
else
t[i].add += t[p].add; //没set加给add
t[i].mx += t[p].add;
}
if (t[p].set != -INF)
t[i].mx = t[i].set = t[p].set,
t[i].add = 0; // set覆盖就完事了,add没用了直接清零
t[i].hset = std::max(t[i].set, t[i].hset);
t[i].hadd = std::max(t[i].add, t[i].hadd);
}
t[p].set = t[p].hset = -INF, t[p].add = t[p].hadd = 0;
}

void Build(int p, int l, int r) {
t[p] = {l, r, 0, 0, -INF, -INF, -INF, -INF};
if (l == r) return (void)(t[p].mx = t[p].hmx = a[l]);
int mid = (l + r) >> 1;
Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r);
t[p].mx = t[p].hmx = std::max(t[p << 1].mx, t[p << 1 | 1].mx);
}

int query_now(int p, int l, int r) {
if (t[p].l != t[p].r) pushdown(p);
if (l <= t[p].l && r >= t[p].r) return t[p].mx;
int mid = (t[p].l + t[p].r) >> 1, ret = -INF;
if (l <= mid) ret = std::max(ret, query_now(p << 1, l, r));
if (r > mid) ret = std::max(ret, query_now(p << 1 | 1, l, r));
pushup(p);
return ret;
}

int query_history(int p, int l, int r) {
if (t[p].l != t[p].r) pushdown(p);
if (l <= t[p].l && r >= t[p].r) return t[p].hmx;
int mid = (t[p].l + t[p].r) >> 1, ret = -INF;
if (l <= mid) ret = std::max(ret, query_history(p << 1, l, r));
if (r > mid) ret = std::max(ret, query_history(p << 1 | 1, l, r));
pushup(p);
return ret;
}

void add(int p, int l, int r, int d) {
if (t[p].l != t[p].r) pushdown(p);
if (l <= t[p].l && r >= t[p].r)
return (void)(t[p].add += d, t[p].hadd += d, t[p].mx += d,
t[p].hmx = std::max(t[p].hmx, t[p].mx));
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) add(p << 1, l, r, d);
if (r > mid) add(p << 1 | 1, l, r, d);
pushup(p);
}

void change(int p, int l, int r, int d) {
if (t[p].l != t[p].r) pushdown(p);
if (l <= t[p].l && r >= t[p].r)
return (void)(t[p].set = t[p].mx = t[p].hset = d,
t[p].hmx = std::max(t[p].hmx, t[p].mx));
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) change(p << 1, l, r, d);
if (r > mid) change(p << 1 | 1, l, r, d);
pushup(p);
}

signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
Build(1, 1, n);
for (int i = 1; i <= m; i++) {
char op[5];
int x, y, z;
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'Q')
printf("%d\n", query_now(1, x, y));
else if (op[0] == 'A')
printf("%d\n", query_history(1, x, y));
else if (op[0] == 'P')
scanf("%d", &z), add(1, x, y, z);
else if (op[0] == 'C')
scanf("%d", &z), change(1, x, y, z);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×