洛谷4314 cpu监控

首先我们可以想到一个显而易见的思路:每个节点维护$\mathrm{add,set}$的$tag$,维护最大值$max$和历史最大值$Max$,然后像正常的线段树一样维护

然后你惊讶的发现你只拿到二十分(只有$Q$的部分分)

为什么呢?我们发现有些$tag$,他还没有来得及被更新就被覆盖了..而这些$tag$本来能改变世界更新答案

所以我们可以维护两个$tag$:$\mathrm{Add,Set}$表示该节点从上次下放到目前的最大$add$和$set$值

然后我们就可以快乐的用这些$tag$来维护答案了

Code:

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) ((a + b) % mod)
#define checkmax(a, b) ((a) = ((a) < (b)) ? (b) : (a))

const int MaxN = 1e5 + 10;
const int inf = 0x3f3f3f3f;

struct node
{
int l, r;
int Max, Add, Set;
int max, add, set;
};

int n, m, a[MaxN];

struct SegmentTree
{
node t[MaxN << 2];
inline void pushup(int id)
{
t[id].max = std::max(t[id << 1].max, t[id << 1 | 1].max);
t[id].Max = std::max(t[id << 1].Max, t[id << 1 | 1].Max);
}
inline void build(int id, int l, int r)
{
t[id].l = l, t[id].r = r, t[id].set = t[id].Set = -inf;
if (l == r)
{
t[id].max = t[id].Max = a[(l + r) >> 1];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
pushup(id);
}
inline void checksum(int id, int add, int Add)
{
if (t[id].set != -inf)
{
checkmax(t[id].Set, t[id].set + Add);
checkmax(t[id].Max, t[id].max + Add);
t[id].set += add, t[id].max += add;
}
else
{
checkmax(t[id].Add, t[id].add + Add);
checkmax(t[id].Max, t[id].max + Add);
t[id].add += add, t[id].max += add;
}
}
inline void checkset(int id, int set, int Set)
{
checkmax(t[id].Set, Set);
checkmax(t[id].Max, Set);
t[id].set = set, t[id].max = set;
}
inline void pushdown(int id)
{
checksum(id << 1, t[id].add, t[id].Add), checksum(id << 1 | 1, t[id].add, t[id].Add), t[id].add = t[id].Add = 0;
if (t[id].set != -inf)
{
checkset(id << 1, t[id].set, t[id].Set), checkset(id << 1 | 1, t[id].set, t[id].Set);
t[id].set = t[id].Set = -inf;
}
}
void add(int id, int l, int r, int val)
{
if (t[id].l > r || t[id].r < l)
return;
if (l <= t[id].l && t[id].r <= r)
{
checksum(id, val, val);
return;
}
pushdown(id), add(id << 1, l, r, val), add(id << 1 | 1, l, r, val), pushup(id);
}
void set(int id, int l, int r, int val)
{
if (t[id].l > r || t[id].r < l)
return;
if (l <= t[id].l && t[id].r <= r)
{
checkset(id, val, val);
return;
}
pushdown(id), set(id << 1, l, r, val), set(id << 1 | 1, l, r, val), pushup(id);
}
int query_max(int id, int l, int r)
{
if (t[id].l > r || t[id].r < l)
return -inf;
if (l <= t[id].l && t[id].r <= r)
return t[id].max;
pushdown(id);
return std::max(query_max(id << 1, l, r), query_max(id << 1 | 1, l, r));
}
int query_Max(int id, int l, int r)
{
if (t[id].l > r || t[id].r < l)
return -inf;
if (l <= t[id].l && t[id].r <= r)
return t[id].Max;
pushdown(id);
return std::max(query_Max(id << 1, l, r), query_Max(id << 1 | 1, l, r));
}
} T;

char get()
{
char ch = getchar();
while (ch > 'Z' || ch < 'A')
ch = getchar();
return ch;
}

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
T.build(1, 1, n);
scanf("%d", &m);
while (m--)
{
char ch = get();
int x = read(), y = read(), z;
if (ch == 'Q')
printf("%d\n", T.query_max(1, x, y));
else if (ch == 'A')
printf("%d\n", T.query_Max(1, x, y));
else if (ch == 'P')
z = read(), T.add(1, x, y, z);
else
z = read(), T.set(1, x, y, z);
}
return 0;
}
Your browser is out-of-date!

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

×