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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
using namespace std;
const int N = 100005;
int add[4 * N], maxv[4 * N];
void pushup(int p)
{
maxv[p] = max(maxv[p << 1], maxv[p << 1 | 1]);
}
void pushdown(int p)
{
add[p << 1] += add[p];
add[p << 1 | 1] += add[p];
maxv[p << 1] += add[p];
maxv[p << 1 | 1] += add[p];
add[p] = 0;
}
void build(int p, int s, int e)
{
add[p] = 0;
if(s == e) scanf("%d", &maxv[p]);
else
{
build(lc);
build(rc);
pushup(p);
}
}
void update(int p, int s, int e, int l, int r, int v, int op)
{
if(s == l && e == r)
{
if(op)
{
add[p] += v;
maxv[p] += v;
}
else maxv[p] = v;
return;
}
pushdown(p);
if(r <= mid) update(lc, l, r, v, op);
else if(l > mid) update(rc, l, r, v, op);
else update(lc, l, mid, v, op), update(rc, mid + 1, r, v, op);
pushup(p);
}
int query(int p, int s, int e, int l, int r)
{
if(s == l && e == r) return maxv[p];
pushdown(p);
if(r <= mid) return query(lc, l, r);
if(l > mid) return query(rc, l, r);
return max(query(lc, l, mid), query(rc, mid + 1, r));
}
int main()
{
int n, m, x, y;
char cmd[10];
while(~scanf("%d%d", &n, &m))
{
build(1, 1, n);
while(m--)
{
scanf("%s", cmd);
if(!strcmp(cmd, "Ask"))
{
scanf("%d", &x);
printf("%d\n", query(1, 1, n, x + 1, x + 1));
continue;
}
scanf("%d%d", &x, &y);
if(cmd[0] == 'Q')
printf("%d\n", query(1, 1, n, x + 1, y + 1));
else if(cmd[0] == 'C')
update(1, 1, n, x + 1, x + 1, y, 0);
else
update(1, 1, n, x + 1, y + 1, 1, 1);
}
}
return 0;
}
|