大半年时间没练习,已经什么也不会了 ==
为了维护区间最大子区间和,容易想到线段树区间合并,需要维护包含左/右端点的最大子区间和。
至于环状结构,可以通过二选一来等价得到答案,因此还需要维护区间最小子区间和。
注意特判不能全选。
#include <algorithm> #include <cstdio> #include <iostream> using namespace std; const int maxn(1e5 + 10); int a[maxn]; struct node { // 左(右)子编号,区间和 int l, r, sum; // 区间内的最小(大)子区间和 int mn, mx; // 区间内包含左端的最小(大)子区间和 int lmn, lmx; // 区间内包含右端的最小(大)子区间和 int rmn, rmx; } tree[maxn << 2]; inline int ls(int cur) { return cur << 1; } inline int rs(int cur) { return cur << 1 xor 1; } void push_up(int cur) { tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum; // 继承左子或右子拼接左子 tree[cur].lmn = min(tree[ls(cur)].lmn, tree[rs(cur)].lmn + tree[ls(cur)].sum); tree[cur].lmx = max(tree[ls(cur)].lmx, tree[rs(cur)].lmx + tree[ls(cur)].sum); // 继承右子或左子拼接右子 tree[cur].rmn = min(tree[rs(cur)].rmn, tree[ls(cur)].rmn + tree[rs(cur)].sum); tree[cur].rmx = max(tree[rs(cur)].rmx, tree[ls(cur)].rmx + tree[rs(cur)].sum); // 继承左右子或左右子拼接 tree[cur].mn = min(min(tree[ls(cur)].mn, tree[rs(cur)].mn), tree[ls(cur)].rmn + tree[rs(cur)].lmn); tree[cur].mx = max(max(tree[ls(cur)].mx, tree[rs(cur)].mx), tree[ls(cur)].rmx + tree[rs(cur)].lmx); } void build(int cur, int l, int r) { tree[cur].l = l; tree[cur].r = r; if (l == r) { tree[cur].sum = tree[cur].mn = tree[cur].mx = \ tree[cur].lmn = tree[cur].lmx = tree[cur].rmn = tree[cur].rmx = a[l]; return; } int mid = (l + r) >> 1; build(ls(cur), l, mid); build(rs(cur), mid + 1, r); push_up(cur); } void update(int cur, int p, int v) { if (tree[cur].l == p and tree[cur].r == p) { tree[cur].sum = tree[cur].mn = tree[cur].mx = \ tree[cur].lmn = tree[cur].lmx = tree[cur].rmn = tree[cur].rmx = v; return; } int mid = (tree[cur].l + tree[cur].r) >> 1; if (p <= mid) { update(ls(cur), p, v); } else { update(rs(cur), p, v); } push_up(cur); } int query() { int mx = max(tree[1].mx, tree[1].sum - tree[1].mn); // 不能全选 return mx == tree[1].sum ? mx - tree[1].mn : mx; } int main() { #ifdef ONLINE_JUDGE #else freopen("input.txt", "r", stdin); #endif int n, m, p, v; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } build(1, 1, n); scanf("%d", &m); while (m--) { scanf("%d%d", &p, &v); update(1, p, v); printf("%d\n", query()); } return 0; }