SP1716 GSS3 - Can you answer these queries III

算法

线段树

思路

题目要求维护支持单点修改和查询区间最大子段和的数据结构。考虑使用线段树维护。对于区间 $[l_1,r_1], [l_2,r_2]$ ，合并后的最大子段和有一下三种情况：

区间 $[l_1,r_1]$ 的最大子段和。
区间 $[l_2,r_2]$ 的最大子段和。
跨过中间，区间 $[l_1,r_1]$ 的右边部分和区间 $[l_2,r_2]$ 的左边部分合并后的最大子段和。

所以线段树要维护的信息有四个：

区间和
区间最大子段和
区间左侧最大子段和。
区间右侧最大子段和。

对以上四个信息分别维护即可。

代码

1
#include <bits/stdc++.h>
2

3
constexpr int N = 5e4 + 5;
4
int n, m, op, l, r, arr[N];
5

6
class SegmentTree {
7
 protected:
8
  class Values {
9
   public:
10
    int sum = 0, max = 0, left_max = 0, right_max = 0;
11

12
    Values() = default;
13

14
    Values(int x) {
15
      sum = x;
16
      max = x;
17
      left_max = x;
18
      right_max = x;
19
    }
20
  };
21

22
  class Node {
23
   public:
24
    int l, r;
25
    Values val;
26
  };
27

28
  Node tr[N << 2];
29

30
 public:
31
  Values merge(Values a, Values b) {
32
    Values retval;
33

34
    retval.sum = a.sum + b.sum;
35
    retval.max = std::max({a.max, b.max, a.right_max + b.left_max});
36
    retval.left_max = std::max(a.left_max, a.sum + b.left_max);
37
    retval.right_max = std::max(b.right_max, b.sum + a.right_max);
38

39
    return retval;
40
  }
41

42
  void push_up(int k) {
43
    Values lc = tr[k << 1].val, rc = tr[k << 1 | 1].val;
44
    tr[k].val = merge(lc, rc);
45
  }
46

47
  void build_tree(int k, int l, int r) {
48
    tr[k].l = l, tr[k].r = r;
49
    tr[k].val = Values(0);
50

51
    if (tr[k].l == tr[k].r) {
52
      tr[k].val = Values(arr[l]);
53
      return void();
54
    }
55

56
    int mid = (tr[k].l + tr[k].r) >> 1;
57
    int lc = k << 1, rc = k << 1 | 1;
58

59
    build_tree(lc, l, mid);
60
    build_tree(rc, mid + 1, r);
61

62
    push_up(k);
63
  }
64

65
  void modify(int k, int pos, int value) {
66
    if (tr[k].l == tr[k].r && tr[k].r == pos) {
67
      tr[k].val = Values(value);
68
      return void();
69
    }
70

71
    int mid = (tr[k].l + tr[k].r) >> 1;
72
    int lc = k << 1, rc = k << 1 | 1;
73

74
    if (pos <= mid) {
75
      modify(lc, pos, value);
76
    } else {
77
      modify(rc, pos, value);
78
    }
79

80
    push_up(k);
81
  }
82

83
  Values query(int k, int l, int r) {
84
    if (tr[k].l >= l && tr[k].r <= r) {
85
      return tr[k].val;
86
    }
87

88
    int mid = (tr[k].l + tr[k].r) >> 1;
89
    int lc = k << 1, rc = k << 1 | 1;
90

91
    if (r <= mid) {
92
      return query(lc, l, r);
93
    } else if (l > mid) {
94
      return query(rc, l, r);
95
    } else {
96
      return merge(query(lc, l, mid), query(rc, mid + 1, r));
97
    }
98
  }
99
} segment_tree;
100

101
int main() {
102
  std::ios::sync_with_stdio(false);
103
  std::cin.tie(nullptr);
104
  std::cout.tie(nullptr);
105

106
  std::cin >> n;
107

108
  for (int i = 1; i <= n; i++) {
109
    std::cin >> arr[i];
110
  }
111

112
  segment_tree.build_tree(1, 1, n);
113

114
  std::cin >> m;
115

116
  while (m--) {
117
    std::cin >> op >> l >> r;
118

119
    if (op == 0) {
120
      segment_tree.modify(1, l, r);
121
    } else if (op == 1) {
122
      std::cout << segment_tree.query(1, l, r).max << '\n';
123
    }
124
  }
125

126
  return 0;
127
}