SPOJ GSS3 - Can you answer these queries III

补题 摸鱼 写博客
半年没怎么做题突然写起来线段树感觉真滴难受 QwQ

传送门:
SPOJ GSS3 - Can you answer these queries III

题意:
给定一组数据, 有多次操作:
  1.查询一段区间内最大的子段和.
  2.修改一个位置上的数据.

1.png

题解:
首先读完题可以发现是区间查询+单点更新的问题. 线段树模型, 之后思考要维护什么内容.
对于每一个区间, 我们可以维护区间的最大子段和, 但是当PushUp更新的时候发现合并时不好处理.
考虑以下情况, 当合并两个区间的最大子段和时,分为三种情况:
    1.最大子段和在左区间
    2.最大子段和在右区间
    3.最大子段和在中间部分
2.png
对于前两种状况, 我们可以直接取其中较大值即可, 对于第三种情况特殊考虑.
当最大子段和在两区间之间时, 必定会由左侧区间的后缀和右侧区间的前缀组成. 而想要使组成的子段和最大, 则必定是左侧区间的最大后缀和+右区间的最大前缀和.
3.png
最大子段和部分解决了, 现在来处理之前维护最大子段和用到的前缀和.
以前缀和举例, 当合并后最大前缀和有两种情况:
    1.最大前缀和都在左侧区间内.
    2.最大前缀和包括右侧区间的一部分.
4.png
当第一种情况时直接处理, 第二种情况时最大前缀和等于左侧区间的和+右侧区间的最大前缀和

至此, 我们就已经知道线段树所要维护的所有信息:
    1.区间和
    2.区间最大前缀和
    3.区间最大后缀和
    4.区间最大子段和

根据上文的思考, 我们就可以得出如何维护当前节点的信息:

// 更新区间和
T[cur].sum = T[cur << 1].sum + T[cur << 1 | 1].sum;
// 更新前缀和(左区间前缀 或者 右区间前缀+左区间和)
T[cur].per = max(T[cur << 1].per, T[cur << 1].sum + T[cur << 1 | 1].per);
// 更新后缀和(同理)
T[cur].suf = max(T[cur << 1 | 1].suf, T[cur << 1].suf + T[cur << 1 | 1].sum);
// 更新最大子段和 两种情况
// 1.单独在左右区间内
T[cur].con = max(T[cur << 1].con, T[cur << 1 | 1].con);
// 2.在合并的区间中(左区间后缀+右区间前缀)
T[cur].con = max(T[cur].con, T[cur << 1].suf + T[cur << 1 | 1].per);

单点更新就很好实现了, 和线段树板子就差不多了.

代码如下:

Accept C++14 (clang 4.0) 20ms:

/**
 * @author  Moe_Sakiya    sakiya@tun.moe
 * @date    2019-07-23 13:19:44
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

#define leftSon left,mid,cur<<1
#define rightSon mid+1,right,cur<<1|1

const int maxN = 50005;

struct Node
{
    int sum;            // 当前节点的区间和
    int per;            // 当前节点的最大前缀和(前子段和)
    int suf;            // 当前节点的最大后缀和(后子段和)
    int con;            // 当前节点的最大子段和
} T[maxN << 2];

int n, q;

// 向上更新
void PushUp(int cur) {
    // 更新区间和
    T[cur].sum = T[cur << 1].sum + T[cur << 1 | 1].sum;
    // 更新前缀和(左区间前缀 或者 右区间前缀+左区间和)
    T[cur].per = max(T[cur << 1].per, T[cur << 1].sum + T[cur << 1 | 1].per);
    // 更新后缀和(同理)
    T[cur].suf = max(T[cur << 1 | 1].suf, T[cur << 1].suf + T[cur << 1 | 1].sum);
    // 更新最大子段和 两种情况
    // 1.单独在左右区间内
    T[cur].con = max(T[cur << 1].con, T[cur << 1 | 1].con);
    // 2.在合并的区间中(左区间后缀+右区间前缀)
    T[cur].con = max(T[cur].con, T[cur << 1].suf + T[cur << 1 | 1].per);
    return;
}

// 建树
void BuildTree(int left, int right, int cur) {
    int mid = (left + right) >> 1;
    if (left == right) {
        scanf("%d", &T[cur].sum);
        T[cur].suf = T[cur].per = T[cur].con = T[cur].sum;
        return;
    }
    BuildTree(leftSon);
    BuildTree(rightSon);
    PushUp(cur);
    return;
}

// 修改
void UpdateNode(int node, int value, int left, int right, int cur) {
    int mid = (left + right) >> 1;
    if (left == right) {
        T[cur].suf = T[cur].per = T[cur].con = T[cur].sum = value;
        return;
    }
    if (node <= mid)
        UpdateNode(node, value, leftSon);
    else
        UpdateNode(node, value, rightSon);
    PushUp(cur);
    return;
}

// 查询
Node QuerySection(int leftSection, int rightSection, int left, int right, int cur) {
    int mid = (left + right) >> 1;
    // 当前节点完全在查询区间内
    if (leftSection <= left && right <= rightSection)
        return T[cur];
    // 当前节点不在查询区间内 向下递归
    if (mid < leftSection)
        return QuerySection(leftSection, rightSection, rightSon);
    else if (rightSection <= mid)
        return QuerySection(leftSection, rightSection, leftSon);
    // 当前节点部分在查询区域内 取左右子树合并求解(类似PushUp操作)
    Node retNode, leftNode, rightNode;
    leftNode = QuerySection(leftSection, rightSection, leftSon);
    rightNode = QuerySection(leftSection, rightSection, rightSon);
    // 合并区间结果
    retNode.sum = leftNode.sum + rightNode.sum;
    retNode.per = max(leftNode.per, leftNode.sum + rightNode.per);
    retNode.suf = max(rightNode.suf, leftNode.suf + rightNode.sum);
    retNode.con = max(leftNode.con, rightNode.con);
    retNode.con = max(retNode.con, leftNode.suf + rightNode.per);
    return retNode;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int cmd, l, r;
    scanf("%d", &n);
    BuildTree(1, n, 1);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d %d", &cmd, &l, &r);
        switch (cmd) {
        case 0:
            UpdateNode(l, r, 1, n, 1);
            break;
        case 1:
            printf("%d\n", QuerySection(l, r, 1, n, 1).con);
            break;
        }
    }
    return 0;
}

添加新评论

captcha
请输入验证码