bzoj3064 Tyvj 1518 CPU监控

Description

Bob需要一个程序来监视CPU使用率。这是一个很繁琐的过程,为了让问题更加简单,Bob会慢慢列出今天会在用计算机时做什么事。
Bob会干很多事,除了跑暴力程序看视频之外,还会做出去玩玩和用鼠标乱点之类的事,甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内CPU使用率增加或减少一个值;有的事还会直接让CPU使用率变为一个值。
当然Bob会询问:在之前给出的事件影响下,CPU在某段时间内,使用率最高是多少。有时候Bob还会好奇地询问,在某段时间内CPU曾经的最高使用率是多少。
为了使计算精确,使用率不用百分比而用一个整数表示。
不保证Bob的事件列表出了莫名的问题,使得使用率为负………………

Input

第一行一个正整数T,表示Bob需要监视CPU的总时间。
然后第二行给出T个数表示在你的监视程序执行之前,Bob干的事让CPU在这段时间内每个时刻的使用率达已经达到了多少。
第三行给出一个数E,表示Bob需要做的事和询问的总数。
接下来E行每行表示给出一个询问或者列出一条事件:
Q X Y:询问从X到Y这段时间内CPU最高使用率
A X Y:询问从X到Y这段时间内之前列出的事件使CPU达到过的最高使用率
P X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率增加Z
C X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率变为Z
时间的单位为秒,使用率没有单位。
X和Y均为正整数(X<=Y),Z为一个整数。
从X到Y这段时间包含第X秒和第Y秒。
保证必要运算在有符号32位整数以内。

Output

对于每个询问,输出一行一个整数回答。

Sample Input

10
-62 -83 -9 -70 79 -78 -31 40 -18 -5
20
A 2 7
A 4 4
Q 4 4
P 2 2 -74
P 7 9 -71
P 7 10 -8
A 10 10
A 5 9
C 1 8 10
Q 6 6
Q 8 10
A 1 7
P 9 9 96
A 5 5
P 8 10 -53
P 6 6 5
A 10 10
A 4 4
Q 1 5
P 4 9 -69

Sample Output

79
-70
-70
-5
79
10
10
79
79
-5
10
10

HINT

数据分布如下:
第1、2个数据保证T和E均小于等于1000
第3、4个数据保证只有Q类询问
第5、6个数据保证只有C类事件
第7、8个数据保证只有P类事件
全部数据保证T和E均小于等于100000

Source

题解

一道毒瘤的线段树pushdown操作练习题。由于过于复杂,文字解释先挖个坑,日后再添。

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
#include<bits/stdc++.h>
#define ps puts("")
#define fi first
#define nd second
#define mset(x) memset((x), 0, sizeof (x))
#define mk make_pair
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
ll read() {ll x = 0;char f = 1, ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-')f = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 150000;
#define mid ((ls[o] + rs[o]) >> 1)
#define lch (o<<1)
#define rch (o<<1|1)
int a[N], n, ls[N * 4], rs[N * 4];
const int inf = 1e9;
ll mx[N * 4], ad[N * 4], tag[N * 4];
ll tad[N * 4], tmx[N * 4], ttag[N * 4];
void up(int o) {
mx[o] = max(mx[lch], mx[rch]);
tmx[o] = max(tmx[lch], tmx[rch]);
}
void build(int o, int l, int r) {
ls[o] = l, rs[o] = r;
tag[o] = ttag[o] = -inf;
if(l == r) {
mx[o] = tmx[o] = a[l];
return;
}
if(l <= mid) build(lch, l, mid );
if(r > mid) build(rch, mid + 1, r);
up(o);
}
void TAD(int o, ll v) {
tmx[o] = max(tmx[o], mx[o] + v);
if(tag[o] != -inf) ttag[o] = max(ttag[o], tag[o] + v);
else tad[o] = max(tad[o], ad[o] + v);
}
void TTAG(int o, ll v) {
ttag[o] = max(ttag[o], v);
tmx[o] = max(tmx[o], v);
}
void AD(int o, ll v) {
tmx[o] = max(tmx[o], mx[o] += v);
if(tag[o] > -inf) ttag[o] = max(ttag[o], tag[o] += v);
else tad[o] = max(tad[o], ad[o] += v);
}
void TAG(int o, ll v) {
tmx[o] = max(tmx[o], mx[o] = v);
ttag[o] = max(ttag[o], tag[o] = v);
ad[o] = 0;
}
void down(int o) {
if(tad[o]) {
TAD(lch, tad[o]);
TAD(rch, tad[o]);
tad[o] = 0;
}
if(ttag[o] != -inf) {
TTAG(lch,ttag[o]);
TTAG(rch,ttag[o]);
ttag[o] = -inf;
}
if(ad[o]) {
AD(lch, ad[o]);
AD(rch, ad[o]);
ad[o] = 0;
}
if(tag[o] != -inf) {
TAG(lch, tag[o]);
TAG(rch, tag[o]);
tag[o] = -inf;
}
}
void change(int o, int l, int r , ll v) { // 加
if(l <= ls[o] && r >= rs[o]) {
AD(o,v);
return;
}
down(o);
if(l <= mid) change(lch, l, r, v);
if(r > mid) change(rch, l, r, v);
up(o);
}
void _change(int o, int l, int r, ll v) { //替换
if(l <= ls[o] && r >= rs[o]) {
TAG(o,v);
return ;
}
down(o);
if(l <= mid) _change(lch, l, r, v);
if(r > mid) _change(rch, l, r, v);
up(o);
}
ll askall(int o, int l, int r) {
if(l <= ls[o] && r >= rs[o])
return tmx[o];
down(o);
if(r <= mid) return askall(lch,l,r);
if(l > mid) return askall(rch, l, r);
return max(askall(lch,l,r), askall(rch, l, r));
}
ll askmx(int o, int l, int r) {
if(l <= ls[o] && r >= rs[o])
return mx[o];
down(o);
if(r <= mid) return askmx(lch,l,r);
if(l > mid) return askmx(rch, l, r);
return max(askmx(lch,l,r), askmx(rch, l, r));
}
char op[6];
int x, y;
ll z;
int main() {
n = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
build(1, 1, n);
int m = read();
for(int T = 1; T <= m; ++T){
scanf("%s", op + 1);
x = read(), y = read();
if(op[1] == 'Q') {
writeln(askmx(1, x, y));
} else if(op[1] == 'A') {
writeln(askall(1, x, y));
} else if(op[1] == 'P') {
z = read();
change(1, x, y, z);
} else {
z = read();
_change(1, x, y, z);
}
}
return 0;
}