线段树-区间最大连续和 NKOJ1316 (小白逛公园)

 1 #include <stdio.h>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 const int _N = 550000;
 7 const int INF = 1e9;
 8 
 9 int A[_N];
10 int n, m;
11 
12 struct node {
13     int l, r, c_l, c_r, max, sum, mid;
14     void set_lr(int _l, int _r) { l = _l; r = _r; mid = l+r>>1; return; }
15     void set_val(int _v) { c_l = c_r = max = sum = _v; return; }
16 } T[_N << 3];
17 
18 void _update(int p)
19 {
20     T[p].c_l = max(T[p<<1].c_l, T[p<<1].sum+T[p<<1|1].c_l);
21     T[p].c_r = max(T[p<<1|1].c_r, T[p<<1|1].sum+T[p<<1].c_r);
22     T[p].max = max(max(T[p<<1].max, T[p<<1|1].max), T[p<<1].c_r+T[p<<1|1].c_l);
23     T[p].sum = T[p<<1].sum + T[p<<1|1].sum;
24     return;
25 }
26 
27 void _init(int p, int x, int y)
28 {
29     T[p].set_lr(x, y);
30     if (x == y){ T[p].set_val(A[x]); return; }
31     _init(p<<1, x, T[p].mid), _init(p<<1|1, T[p].mid+1, y);
32     _update(p);
33     return;
34 }
35 
36 //返回 [x, y] 中从线段 p 左端开始的连续最大和 
37 int _begin_l(int p, int y)
38 {
39     if (T[p].r <= y) return T[p].c_l;
40     if (y <= T[p].mid) return _begin_l(p<<1, y);
41     return max(_begin_l(p<<1, y), T[p<<1].sum+_begin_l(p<<1|1, y));
42 }
43 
44 int _begin_r(int p, int x)
45 {
46     if (T[p].l >= x) return T[p].c_r;
47     if (x > T[p].mid) return _begin_r(p<<1|1, x);
48     return max(_begin_r(p<<1|1, x), T[p<<1|1].sum+_begin_r(p<<1, x));
49 }
50 
51 int _query(int p, int x, int y)
52 {
53     if (x <= T[p].l && T[p].r <= y) return T[p].max;
54     int maxx = -INF;
55     if (x <= T[p].mid && y >= T[p].l) maxx = max(maxx, _query(p<<1, x, y));
56     if (x <= T[p].r && y > T[p].mid) maxx = max(maxx, _query(p<<1|1, x, y));
57     if (x <= T[p].mid && T[p].mid < y) maxx = max(maxx, _begin_r(p<<1, x)+_begin_l(p<<1|1, y));
58     return maxx;
59 }
60 
61 void _modify(int p, int x, int y)
62 {
63     if (T[p].l == T[p].r) { T[p].set_val(y); return ; }
64     if (x <= T[p].mid) _modify(p<<1, x, y);
65     else _modify(p<<1|1, x, y);
66     _update(p);
67     return;
68 }
69 
70 int main()
71 {
72     int i;
73     scanf("%d%d", &n, &m);
74     for (i = 1; i <= n; ++i)
75         scanf("%d", &A[i]);
76     _init(1, 1, n);
77     while (m--) {
78         int ins, t1, t2;
79         scanf("%d%d%d", &ins, &t1, &t2);
80         if (ins == 1)
81             printf("%d
", t1 <= t2 ? _query(1, t1, t2) : _query(1, t2, t1));
82         else
83             _modify(1, t1, t2);
84     }
85     return 0;
86 }