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
| import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static Node[] tr;
static int[] A;
public static void main(String[] agrs) throws Exception{
String[] strs = br.readLine().split(" ");
int n = Integer.valueOf(strs[0]);
int m = Integer.valueOf(strs[1]);
tr = new Node[4*n];
strs = br.readLine().split(" ");
A = new int[n+1];
for(int i = 1; i <= n; i++){
A[i] = Integer.valueOf(strs[i-1]);
}
build(1, 1, n);
while(m-- > 0){
strs = br.readLine().split(" ");
int k = Integer.valueOf(strs[0]);
int x = Integer.valueOf(strs[1]);
int y = Integer.valueOf(strs[2]);
if(k == 1){
if(x>y){
int tmp = 0;
tmp = x;
x = y;
y = tmp;
}
Node node = query(1, x, y);
bw.write(node.tmax + "\n");
}else{
modify(1, x, y);
}
}
bw.flush();
}
static void modify(int u, int x, int c){
if(tr[u].l == x && tr[u].r == x){
tr[u].sum = c;
tr[u].lmax = c;
tr[u].rmax = c;
tr[u].tmax = c;
}else{
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid){
modify(u << 1, x, c);
}else{
modify(u << 1|1, x, c);
}
pushUp(u);
}
}
static Node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r){
return tr[u];
}
int mid = (tr[u].l+tr[u].r) >> 1;
if(r<= mid){
return query(u << 1, l, r);
}else if(l > mid){
return query(u << 1|1, l, r);
}else{
Node left = query(u << 1, l, r);
Node right = query(u << 1|1, l, r);
Node root = new Node(l, r);
pushUp(root, left, right);
return root;
}
}
static void build(int u, int l, int r){
if(l == r){
tr[u] = new Node(l, r, A[l], A[l], A[l], A[l]);
}else{
tr[u] = new Node(l, r);
int mid = (l + r) >> 1;
build(u << 1, l , mid);
build(u << 1 | 1, mid + 1, r);
pushUp(u);
}
}
static void pushUp(int u){
pushUp(tr[u], tr[u<<1], tr[u<<1|1]);
}
static void pushUp(Node root, Node l, Node r){
root.sum = l.sum + r.sum;
root.lmax = Math.max(l.lmax, l.sum + r.lmax);
root.rmax = Math.max(r.rmax, r.sum + l.rmax);
root.tmax = Math.max(Math.max(l.tmax, r.tmax), l.rmax + r.lmax);
}
static class Node{
int l;
int r;
int sum;
int lmax;
int rmax;
int tmax;
Node(int l, int r){
this.l = l;
this.r = r;
}
Node(int l, int r, int sum, int lmax, int rmax, int tmax){
this.l = l;
this.r = r;
this.sum = sum;
this.lmax = lmax;
this.rmax = rmax;
this.tmax = tmax;
}
}
}
|
