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
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) print('0');
else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 100005, inf = 0x7fffffff;
int n, m, a[N], add[N<<2], madd[N<<2], cov[N<<2], mcov[N<<2], mx[N<<2], mmx[N<<2];
inline void chkmx(int &x, int y){ x<y?x=y:0;}
inline void pushdown(int t){
int k=t<<1;
if(add[t] || madd[t]){
chkmx(mmx[k], mx[k]+madd[t]), mx[k]+=add[t];
if(cov[k]!=-inf) chkmx(mcov[k], cov[k]+madd[t]), cov[k]+=add[t]; else chkmx(madd[k], add[k]+madd[t]), add[k]+=add[t];
chkmx(mmx[k|1], mx[k|1]+madd[t]), mx[k|1]+=add[t];
if(cov[k|1]!=-inf) chkmx(mcov[k|1], cov[k|1]+madd[t]), cov[k|1]+=add[t]; else chkmx(madd[k|1], add[k|1]+madd[t]), add[k|1]+=add[t];
}
if(cov[t]!=-inf){
chkmx(mmx[k], mcov[t]), mx[k]=cov[t];
add[k]=0, chkmx(mcov[k], mcov[t]), cov[k]=cov[t];
chkmx(mmx[k|1], mcov[t]), mx[k|1]=cov[t];
add[k|1]=0, chkmx(mcov[k|1], mcov[t]), cov[k|1]=cov[t];
}
add[t]=madd[t]=0, cov[t]=mcov[t]=-inf;
}
inline void update(int t){
int k=t<<1;
mx[t]=max(mx[k], mx[k|1]);
mmx[t]=max(mmx[k], mmx[k|1]);
}
void build(int l, int r, int t){
madd[t]=add[t]=0, mcov[t]=cov[t]=-inf;
if(l==r) return (void)(mmx[t]=mx[t]=a[l]);
int mid=l+r>>1, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
mmx[t]=mx[t]=max(mx[k], mx[k|1]);
}
void Plus(int l, int r, int t, int L, int R, int x){
if(L<=l && r<=R) return chkmx(mmx[t], mx[t]+=x), cov[t]==-inf?chkmx(madd[t], add[t]+=x):chkmx(mcov[t], cov[t]+=x);
int mid=l+r>>1, k=t<<1;
pushdown(t);
if(L<=mid) Plus(l, mid, k, L, R, x);
if(R>mid) Plus(mid+1, r, k|1, L, R, x);
update(t);
}
void change(int l, int r, int t, int L, int R, int x){
if(L<=l && r<=R) return chkmx(mmx[t], mx[t]=x), add[t]=0, chkmx(mcov[t], cov[t]=x);
int mid=l+r>>1, k=t<<1;
pushdown(t);
if(L<=mid) change(l, mid, k, L, R, x);
if(R>mid) change(mid+1, r, k|1, L, R, x);
update(t);
}
int query1(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return mx[t];
int mid=l+r>>1, k=t<<1;
pushdown(t);
return max(L<=mid?query1(l, mid, k, L, R):-inf, R>mid?query1(mid+1, r, k|1, L, R):-inf);
}
int query2(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return mmx[t];
int mid=l+r>>1, k=t<<1;
pushdown(t);
return max(L<=mid?query2(l, mid, k, L, R):-inf, R>mid?query2(mid+1, r, k|1, L, R):-inf);
}
int main() {
read(n);
for(int i=1; i<=n; ++i) read(a[i]);
build(1, n, 1);
read(m);
while(m--){
static char opt;
static int x, y, z;
while(isspace(opt=read()));
read(x), read(y);
if(opt=='Q') print(query1(1, n, 1, x, y)), print('\n');
else if(opt=='A') print(query2(1, n, 1, x, y)), print('\n');
else if(opt=='P') read(z), Plus(1, n, 1, x, y, z);
else read(z), change(1, n, 1, x, y, z);
}
return flush(), 0;
}
|