题目描述

难度分:$2600$

输入$n(2 \leq n \leq 2 \times 10^5)$，长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$，长为$n$的数组$b(-10^9 \leq b[i] \leq 10^9)$，下标从$1$开始。

定义区间$[i,j]$的$cost=a$的子数组$[i,j]$的元素和$+b[i]+b[j]$。特别地，区间$[i,i]$的$cost=a[i] + 2 \times b[i]$。

然后输入$q(1 \leq q \leq 2 \times 10^5)$和$q$个询问，格式如下：

1. 1 p x，把$a[p]$改成$x$。其中$1 \leq p \leq n$，$-10^9 \leq x \leq 10^9$。
2. 2 p x，把$b[p]$改成$x$。其中$1 \leq p \leq n$，$-10^9 \leq x \leq 10^9$。
3. 3 L R，在区间$[L,R]$中选两个不重叠的非空区间，输出这两个区间的$cost$之和的最大值。其中$1 \leq L \lt R \leq n$。

输入样例$1$

7
3 -1 4 -3 2 4 0
0 6 1 0 -3 -2 -1
6
3 1 7
1 2 0
3 3 6
2 5 -3
1 3 2
3 1 5

输出样例$1$

18
7
16

输入样例$2$

10
2 -1 -3 -2 0 4 5 6 2 5
2 -4 -5 -1 6 2 5 -6 4 2
10
3 6 7
1 10 -2
3 5 7
3 2 8
2 1 -5
2 7 4
3 1 3
3 3 8
3 2 3
1 4 4

输出样例$2$

23
28
28
-17
27
-22

算法

状态机DP+线段树优化

状态定义

对于一段区间$[l,r]$，设计状态

1. $f[0]$当前还未选数。
2. $f[1]$进行第一段的选数。
3. $f[2]$第一段选完了。
4. $f[3]$已经选完了第一段，进行第二段选数。
5. $f[4]$两段都选完了。

状态转移

$f[0]$继承之前的状态就行。$f[1]$有两种可能：$i$是第一段的开始，从$f[0]$转移过来；$i$不是第一段的开始，从$f[1]$转移过来。$f[2]$有两种可能：第一段只有一个$i$，那么$i$既是开始也是结束，$b[i]$要加两遍，从$f[0]$转移过来；$i$只是结束，从$f[1]$转移过来。$f[3]$和$f[1]$类似，$i$可以是开始也可以是结束。$f[4]$和$f[2]$类似，可以既是开始也是结束；也可以仅是结束。状态转移方程如下，$f’$表示前一个状态：

1. $f[0]=f’[0]$
2. $f[1]=max(f’[0]+a[i]+b[i],f’[1]+a[i])$
3. $f[2]=max(f’[0]+a[i]+2 \times b[i],f’[1]+a[i]+b[i],f’[2])$
4. $f[3]=max(f’[2]+a[i]+b[i],f’[3]+a[i])$
5. $f[4]=max(f’[2]+a[i]+2 \times b[i],f’[3]+a[i]+b[i],f’[4])$

状态转移矩阵为
$A=\begin{pmatrix} 0 & a[i]+b[i] & a[i]+2 \times b[i] & -\infty & -\infty \\ -\infty & a[i] & a[i]+b[i] & -\infty & -\infty \\ -\infty & -\infty & 0 & a[i]+b[i] & a[i]+2 \times b[i] \\ -\infty & -\infty & -\infty & a[i] & a[i]+b[i] \\ -\infty & -\infty & -\infty & -\infty & 0 \end{pmatrix}$

转移的时候类似矩阵乘法，对于给定的从$i$转移到$j$，枚举左右两个孩子的转移中间点$k$。某段区间$[l,r]$上的答案就是$0$转移到$4$，即$A[0][4]$。

复杂度分析

时间复杂度

建立线段树的时间复杂度为$O(nlog_2n)$。处理$q$个操作。每个操作会有对线段树的修改和查询操作，总的时间复杂度为$O(qlog_2n)$。整个算法的时间复杂度为$(n+q)log_2n$，但由于线段树的每个节点需要维护一个$5 \times 5$的矩阵，所以这个$O(log_2n)$的常数非常大。

空间复杂度

空间瓶颈就是线段树的空间，原本的空间复杂度为$O(4n)$，但每个节点需要维护$5 \times 5$的状态转移矩阵。所以额外空间复杂度为$O(100n)$，是个常数很大的$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
const LL INF = 1e18;
int n, q, a[N], b[N];

class SegmentTree {
public:
    struct Info {
        int l, r;
        LL f[5][5];
        Info() {
            memset(f, -0x3f, sizeof f);
            for(int i = 0; i < 5; i++) {
                f[i][i] = 0;
            }
        }
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u].l = seg[u].r = r;
            LL x = a[l], y = b[l];
            seg[u].f[0][0] = 0;
            seg[u].f[0][1] = x + y;
            seg[u].f[1][1] = x;
            seg[u].f[0][2] = x + 2 * y;
            seg[u].f[1][2] = x + y;
            seg[u].f[2][2] = 0;
            seg[u].f[2][3] = x + y;
            seg[u].f[3][3] = x;
            seg[u].f[2][4] = x + 2 * y;
            seg[u].f[3][4] = x + y;
            seg[u].f[4][4] = 0;
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos) {
        modify(1, pos);
    }

    Info query(int l, int r) {
        return query(1, l, r);
    }

private:
    void modify(int u, int pos) {
        if(seg[u].l == pos && seg[u].r == pos) {
            LL x = a[pos], y = b[pos];
            seg[u].f[0][0] = 0;
            seg[u].f[0][1] = x + y;
            seg[u].f[1][1] = x;
            seg[u].f[0][2] = x + 2 * y;
            seg[u].f[1][2] = x + y;
            seg[u].f[2][2] = 0;
            seg[u].f[2][3] = x + y;
            seg[u].f[3][3] = x;
            seg[u].f[2][4] = x + 2 * y;
            seg[u].f[3][4] = x + y;
            seg[u].f[4][4] = 0;
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) {
                modify(u<<1, pos);
            }else {
                modify(u<<1|1, pos);
            }
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) return seg[u];
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                info.f[i][j] = -INF;
                for(int k = 0; k < 5; k++) {
                    info.f[i][j] = max(info.f[i][j], lchild.f[i][k] + rchild.f[k][j]);
                }
            }
        }
        return info;
    }
};

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    SegmentTree seg;
    seg.build(1, 1, n + 1);
    scanf("%d", &q);
    while(q--) {
        int t;
        scanf("%d", &t);
        if(t < 3) {
            int p, x;
            scanf("%d%d", &p, &x);
            if(t == 1) {
                a[p] = x;
            }else {
                b[p] = x;
            }
            seg.modify(p);
        }else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", seg.query(l, r).f[0][4]);
        }
    }
    return 0;
}