POJ 2750 Potted Flower

传送门

大半年时间没练习，已经什么也不会了 ==

为了维护区间最大子区间和，容易想到线段树区间合并，需要维护包含左/右端点的最大子区间和。

至于环状结构，可以通过二选一来等价得到答案，因此还需要维护区间最小子区间和。

注意特判不能全选。

#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
", query());
    }
    return 0;
}