洛谷 P4513 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-22 12:01:22

发布于：北京

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个公园，每个公园 $i$ 有初始分数 $a_i$ ，接下来要进行 $m$ 次操作
允许：
对于每次操作，有两种可能：

给出两个数 $x$ 和 $y$ ，代表公园编号区间 $[x,y]$ ，求这段区间内的最大连续子段和
给出两个数 $p$ 和 $s$ ，代表将公园 $p$ 的分数设置为 $s$

限制：
每个公园的分数有可能是负数

1.3 题目数据范围与猜测

$1 \le n \le 5\times10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有一些公园，每个公园有初始分数，对于每次操作，如果是设置则无需任何输出，如果是查询则输出特定区间内的最大连续子段和

2 题目破题推导

2.1 大拆小，小组大

还是以区间 $[l,r]$ 为例
我们只需要记录 $4$ 个信息（这些信息并不是提前想出的，而是边扩展的过程中边考虑增加信息的记录，你会发现我们提到的这些信息都是在维护答案的过程中都会用到的）

区间最大连续子段和
区间包含左端点的最大连续子段和
区间包含右端点的最大连续子段和
区间总和

那如何维护这四项呢？

注：这里的左区间是指 $m=\frac{l+r}{2}$ 时的区间 $[l, m]$ ，右区间是指 $m=\frac{l+r}{2}$ 时的区间 $[m+1, r]$

区间最大连续子段和有三种可能
第一种是左区间最大连续子段和
第二种是右区间最大连续子段和
第三种是左区间包含右端点的最大连续子段和与右区间包含左端点的最大连续子段和拼接而成
区间包含左端点的最大连续子段和有两种可能
第一种是左区间包含左端点的最大连续子段和
第二种是左区间总和与右区间包含左端点的最大连续子段和拼接而成
区间包含右端点的最大连续子段和有两种可能
第一种是右区间包含右端点的最大连续子段和
第二种是右区间总和与左区间包含右端点的最大连续子段和拼接而成
区间总和
就是左区间总和 $+$ 右区间总和

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：单点修改，区间查询 $\longrightarrow$ $\huge{线段树}$
注意这题因为不能保证线段树上一定有如 $[2,3]$ 的区间，因此需要新建一个临时结构体用于记录合并，并向上传递答案，最终返回具体值

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define lson (i << 1),l,mid
#define rson (i << 1 | 1),mid + 1,r
#define nlr tree[i],tree[i << 1],tree[i << 1 | 1]
#define all 1,1,n

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}

int n, m;
const int N = 5e5 + 10;
int a[N];
struct node{
    int maxv;
    int maxl, maxr;
    int sum;
}tree[N * 4];
inline void pushup(node &rt, const node &ls, const node &rs){
    if (ls.maxr < 0 && rs.maxl < 0){
        rt.maxv = max(ls.maxr, rs.maxl);
    } else {
        rt.maxv = 0;
        if (ls.maxr >= 0){
            rt.maxv += ls.maxr;
        }
        if (rs.maxl >= 0){
            rt.maxv += rs.maxl;
        }
    }
    rt.maxv = max({rt.maxv, ls.maxv, rs.maxv});
    rt.maxl = max(ls.maxl, ls.sum + rs.maxl);
    rt.maxr = max(rs.maxr, rs.sum + ls.maxr);
    rt.sum = ls.sum + rs.sum;
}
inline void build(int i, int l, int r){
    if (l == r){
        tree[i].maxv = tree[i].maxl = tree[i].maxr = tree[i].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(nlr);
}
inline void update(int p, int s, int i, int l, int r){
    if (l == r){
        tree[i].maxv = tree[i].maxl = tree[i].maxr = tree[i].sum = s;// 为啥
        return ;
    }
    int mid = (l + r) >> 1;
    if (p <= mid){
        update(p, s, lson);
    } else {
        update(p, s, rson);
    }
    pushup(nlr);
}
inline node query(int ql, int qr, int i, int l, int r){
    if (ql <= l && qr >= r){
        return tree[i];
    }
    int mid = (l + r) >> 1;
    if (ql <= mid && qr > mid){
        node res;
        pushup(res, query(ql, qr, lson), query(ql, qr, rson));
        return res;
    } else if (ql <= mid){
        return query(ql, qr, lson);
    } else {
        return query(ql, qr, rson);
    }
}

int main(){

    n = read(), m = read();
    for (int i = 1;i <= n;i++){
        a[i] = read();
    }
    build(all);
    for (int i = 1;i <= m;i++){
        int op = read();
        int fir = read(), sec = read();
        if (op == 1){
            if (fir > sec){
                swap(fir, sec);
            }
            printf("%d\n", query(fir, sec, all).maxv);
        } else {
            update(fir, sec, all);
        }
    }
    
    return 0;
}