最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

AcWing245. 你能回答这些问题吗

来源：博客园

题目描述

给定长度为 \(N\) 的数列 \(A\)，以及 \(M\) 条指令，每条指令可能是以下两种之一：


(资料图片)

  1. 1 x y，查询区间 \([x,y]\) 中的最大连续子段和
  2. 2 x y，把 \(A[x]\) 改成 \(y\)。

对于每个查询指令，输出一个整数表示答案。

解题思路

\(\qquad\)区间问题首选线段树，那这题我们需要维护那些信息呢\(\qquad\)首先我们区间最大连续子段和有三种情况，将一个区间\([l,r]\)分成两部分，那么会有如下\(3\)种情况：

\(\qquad\qquad\large a.\)整个子段在左半边

\(\qquad\qquad\large b.\)整个子段在右半边

\(\qquad\qquad\large c.\)左右都包含了这个子段的一部分

对于上面三种情况，我们进行分类讨论：

\(\qquad\)对于\(a\)情况，我们可以直接取左半部分的值\(\qquad\)对于\(b\)情况也一样。\(\qquad\)对于\(c\)情况，我们可以再次将他拆成左右两段连续的区间，然后维护左半部分的最大后缀和，维护右半部分的最大前缀和，这样这两个东西加起来就是\(c\)情况的最大连续子段和了。

\(\\\)

\(\qquad\qquad\qquad\qquad\LARGE 那如何维护呢？\)

再次分类讨论：一个区间的最大前缀和有两种情况：

\(\qquad\qquad\qquad a.\)全部在左半边

\(\qquad\qquad\qquad b.\)包含了整个左半边和右半边的最大前缀

\(a. 和 b.\)情况取一个\(Max\)即可

对于后缀的维护也是镜像操作。

代码

#include #include #include using namespace std;const int N = 5e5 + 10;int a[N], n, m;struct Seg {    int l, r;    int v, sum, lmax, rmax;} tr[N << 2];void PushUp(Seg& cur, Seg& L, Seg& R) {    cur.sum = L.sum + R.sum;    cur.lmax = max(L.lmax, L.sum + R.lmax);    cur.rmax = max(R.rmax, R.sum + L.rmax);    cur.v = max(L.v, max(R.v, L.rmax + R.lmax));}void pushup(int p) {    PushUp(tr[p], tr[p << 1], tr[p << 1 | 1]);}void build(int p, int l, int r) {    tr[p].l = l, tr[p].r = r;    if (l == r) return void(tr[p] = {l, r, a[l], a[l], a[l], a[l]});        int mid = l + r >> 1;    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);    pushup(p);}void modify(int p, int x, int v) {    int l = tr[p].l, r = tr[p].r;    if (l == x && r == x) return void(tr[p] = {l, r, v, v, v, v});        int mid = l + r >> 1;    if (x <= mid) modify(p << 1, x, v);    else modify(p << 1 | 1, x, v);    pushup(p);}Seg query(int p, int l, int r) {    if (tr[p].l >= l && tr[p].r <= r) return tr[p];        int mid = tr[p].l + tr[p].r >> 1;    if (l > mid) return query(p << 1 | 1, l, r);    if (r <= mid) return query(p << 1, l, r);            Seg L = query(p << 1, l, r);    Seg R = query(p << 1 | 1, l, r);        Seg res;    PushUp(res, L, R);    return res;}int main() {    scanf("%d%d", &n, &m);        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);        build(1, 1, n);        while (m -- )     {        int k, x, y;        scanf("%d%d%d", &k, &x, &y);        if (k == 1) printf("%d\n", query(1, min(x, y), max(x, y)).v);        else modify(1, x, y);    }        return 0;}

关键词： 整数表示 首先我们 我们需要