Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P4513 小白逛公园

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟
标签：    

P4513 小白逛公园

线段树做最大子段和，考虑如何从两个区间合并子段和。

最大子段和可能从下面的情况转移得到：

  • 左区间的最大子段和；
  • 右区间的最大子段和；
  • 左区间最右边开始的最大子段和加上右区间最左边开始的最大子段和。

考虑区间最左边开始的最大子段和如何维护，可能从下面的情况转移得到：

  • 左区间的最左边开始的最大子段和；
  • 左区间的总和加上右区间的最左边开始的最大子段和。

最右边开始的最大子段和同理。

tmx 表示当前区间最大子段和子段和，lmx 表示从当前区间最左边开始的最大子段和，rmx 同理，同时维护区间和 sum 。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
struct Node
{
    LL lmx, rmx, mx, s;
    int l, r;
} tr[N << 2];
int n, m, w[N];
void pushup(Node &x, Node l, Node r)
{
    x.lmx = max(l.lmx, l.s + r.lmx);
    x.rmx = max(r.rmx, r.s + l.rmx);
    x.mx = max(l.rmx + r.lmx, max(l.mx, r.mx));
    x.s = l.s + r.s;
}
void build(int x, int l, int r)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r)
    {
        tr[x].lmx = tr[x].rmx = tr[x].mx = tr[x].s = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(tr[x], tr[x << 1], tr[x << 1 | 1]);
}
void modify(int x, int t, int k)
{
    if (tr[x].l == tr[x].r)
    {
        tr[x].lmx = tr[x].rmx = tr[x].mx = tr[x].s = k;
        return;
    }
    int mid = tr[x].l + tr[x].r >> 1;
    if (t <= mid)
        modify(x << 1, t, k);
    else
        modify(x << 1 | 1, t, k);
    pushup(tr[x], tr[x << 1], tr[x << 1 | 1]);
}
Node query(int x, int l, int r)
{
    if (tr[x].l >= l && tr[x].r <= r)
        return tr[x];
    int mid = tr[x].l + tr[x].r >> 1;
    if (r <= mid)
        return query(x << 1, l, r);
    if (l > mid)
        return query(x << 1 | 1, l, r);
    Node res;
    pushup(res, query(x << 1, l, r), query(x << 1 | 1, l, r));
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    build(1, 1, n);
    for (int op; m; m--)
    {
        scanf("%d", &op);
        if (op == 1)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            if (l > r)
                swap(l, r);
            printf("%lld\n", query(1, l, r).mx);
        }
        else if (op == 2)
        {
            int t, k;
            scanf("%d%d", &t, &k);
            modify(1, t, k);
        }
    }
    return 0;
}
相关文章