P4513 小白逛公园 | answerend42的Blog

题目描述

在小新家附近有一条“公园路”，路的一边从南到北依次排着 $n$ 个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。

一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第 $a$ 个和第 $b$ 个公园之间（包括 $a$、$b$ 两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧。

输入格式

第一行，两个整数 $N$ 和 $M$，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来 $N$ 行，每行一个整数，依次给出小白开始时对公园的打分。
接下来 $M$ 行，每行三个整数。第一个整数 $K$，$1$ 或 $2$。

$K=1$ 表示，小新要带小白出去玩，接下来的两个整数 $a$ 和 $b$ 给出了选择公园的范围（$1≤a,b≤N$）。测试数据可能会出现 $a>b$ 的情况，需要进行交换；
$K=2$ 表示，小白改变了对某个公园的打分，接下来的两个整数 $p$ 和 $s$，表示小白对第 $p$ 个公园的打分变成了 $s$($1\le p \le N$)。
其中，$1\le N \le 5 \times 10^5$，$1 \le M \le 10^5$，所有打分都是绝对值不超过 $1000$ 的整数。

输出格式

小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。

题解

考虑一下不修改的做法，直接暴力跑一遍复杂度是 $\mathcal{O}(n)$ 的，不能直接去做。

维护一段区间的数据结构中，线段树无疑是一个很好的选择。

如果仍然采用暴力查询的方法，本质上复杂度并没有变优，想到朴素方法中只有与上一段相连和另起一段的情况，能否作为我们的解题思路呢？

这就涉及到了线段树上区间之间的合并（当然，单元素也是区间）

对于本题，一段中最大的子段有三种情况：

最大的子段全部在本区间的右侧
最大的子段全部在本区间的左侧
最大的子段越过了本区间的中点

注意到第三种情况一定是包含了本区间的一半，子区间的和是很好维护的，那么只要考虑另一半中选取开头的最大子段。（左区间从右到左的最大子段，右区间从左到右的最大子段）

本题也就被我们解决了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5, inf = 0x3f3f3f3f;
class Tree {
#define ls p << 1
#define rs p << 1 | 1
    struct Node {
        ll ml, mr, mx, sum;
        int l, r;
    } T[N << 2];

public:
    ll a[N];
    void push_up(int p) {
        T[p].sum = T[ls].sum + T[rs].sum, T[p].ml = max(T[ls].ml, T[ls].sum + T[rs].ml),
        T[p].mr = max(T[rs].mr, T[rs].sum + T[ls].mr),
        T[p].mx = max(T[ls].mx, max(T[rs].mx, T[ls].mr + T[rs].ml));
    }
    void build(int p, int l, int r) {
        T[p].l = l, T[p].r = r;
        if (l == r) {
            T[p].sum = T[p].ml = T[p].mr = T[p].mx = a[l];
            return;
        }
        int mid(l + r >> 1);
        build(ls, l, mid);
        build(rs, mid + 1, r);
        push_up(p);
    }
    void update(int p, int x, int y) {
        if (T[p].l == T[p].r) {
            T[p].sum = T[p].ml = T[p].mr = T[p].mx = y;
            return;
        }
        int mid(T[p].l + T[p].r >> 1);
        if (x <= mid)
            update(ls, x, y);
        else
            update(rs, x, y);
        push_up(p);
    }
    Node query(int p, int l, int r) {
        if (l <= T[p].l && T[p].r <= r)
            return T[p];
        int mid(T[p].l + T[p].r >> 1);
        if (r <= mid)
            return query(ls, l, r);
        else if (l > mid)
            return query(rs, l, r);
        else {
            Node x = query(ls, l, r), y = query(rs, l, r), re;
            re.sum = x.sum + y.sum;
            re.ml = max(x.sum + y.ml, x.ml);
            re.mr = max(y.sum + x.mr, y.mr);
            re.mx = max(x.mx, max(y.mx, x.mr + y.ml));
            return re;
        }
    }
};
Tree T;
int n, m;
int op;
ll x, y;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> T.a[i];
    T.build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 1) {
            if (x > y)
                swap(x, y);
            cout << T.query(1, x, y).mx << '\n';
        } else {
            T.update(1, x, y);
        }
    }
    return 0;
}

注意

在本题中计算最终结果时需要用到左区间的最大子段、右区间的最大子段、左区间从右到左的最大子段、右区间从左到右的最大子段，因此要考虑直接返回一个结点
测试数据可能会出现 $a>b$ 的情况，需要进行交换
没有区间修改可以不用加标记

成功的解决了单点修改最大子段，来看看~~区间修改最大子段~~吧。