[Easy-Medium] CF2042F Two Subarrays

xiezheyuan2025/1/28约 1422 字大约 7 分钟

不是，都除夕了，CF 还卡我常数，没有武德！

简要题意

给定两个长度为 $n$ 的序列 $a,b$ ，有 $m$ 次操作，支持：

1 p v 令 $a_p\gets v$ 。
2 p v 令 $b_p\gets v$ 。
3 l r 定义一个区间 $[x,y]$ 的收益为 $b_x+b_y+\sum_{i=x}^{y}a_i$ ，你需要在 $[l,r]$ 中选出两个不交的非空区间，使得这两个区间的收益之和最大，输出这个最大收益和。

$1\leq n,m\leq 2\times 10^5$ 。

思路

先来思考一下这个问题：

给定一个长度为 $n$ 的序列 $a$ ，你需要选出两个不交的非空区间，使得这两个区间的收益之和最大，输出这个最大收益和。 $1\leq n\leq 10^6$ 。

我们称左边的区间为 $A$ 区间，右边的区间为 $B$ 区间，那么实际上对于每一个位置，可以看成进行决策（划分到 $A$ 区间或 $B$ 区间，或者不划分），因此可以考虑 dp。

设 $f(i,x)$ 表示考虑到第 $i$ 个位置的收益和，其中：

$x=1$ 表示在 $i$ 及 $i$ 之前不存在区间的端点。
$x=2$ 表示在 $i$ 及 $i$ 之前存在 $A$ 区间的左端点。
$x=3$ 表示在 $i$ 及 $i$ 之前存在 $A$ 区间的右端点。
$x=4$ 表示在 $i$ 及 $i$ 之前存在 $B$ 区间的左端点。
$x=5$ 表示在 $i$ 及 $i$ 之前存在 $B$ 区间的右端点。

转移的话直接一步一步写就好了：

$f(i,1)=f(i-1,1)$ 。
$f(i,2)=\max(f(i-1,1)+a_i+b_i, f(i-2)+a_i)$ ，表示 $i$ 是否为 $A$ 的左端点。
$f(i,3)=\max(f(i-1,2)+a_i+b_i,f(i-1,1)+a_i+2b_i,f(i-1,3))$ 分别表示 $i$ 仅为 $A$ 的右端点、同时为 $A$ 的左右端点、不为 $A$ 的任何端点。
$f(i,4)=\max(f(i-1,3)+a_i+b_i,f(i-1,4)+a_i)$ ，表示 $i$ 是否为 $B$ 的左端点。
$f(i,5)=\max(f(i-1,4)+a_i+b_i,f(i-1,3)+a_i+2b_i,f(i-1,5))$ 分别表示 $i$ 仅为 $B$ 的右端点、同时为 $B$ 的左右端点、不为 $B$ 的任何端点。

边界 $f(0,1)=0,f(0,2)=f(0,3)=f(0,4)=f(0,5)=-\infty$ ，这样就可以做到 $O(n)$ 了。

回到原问题，有了前面的铺垫，我们很容易看出可以使用动态 dp。

具体地，根据上面的转移方程，可以使用 $(\max,+)$ 矩阵乘法，写出下面的转移矩阵：

P(i-1) \begin{bmatrix} 0 & a_i+b_i & a_i+2b_i & & \\ & a_i & a_i+b_i & & \\ & & 0 & a_i+b_i & a_i+2b_i\\ & & & a_i & a_i+b_i\\ & & & & 0 \end{bmatrix} = P(i)

其中 $P(i)=\begin{bmatrix}f(i,1) & f(i,2) & f(i,3) & f(i,4) & f(i,5)\end{bmatrix}$ 表示状态向量。

于是按照动态 dp 的基本套路，写一个单点修改区间查询矩阵乘积的线段树即可，时间复杂度 $O(m\log n)$ 。可能需要卡常，一种实用的卡常方法是先对矩阵乘法循环展开，然后观察到有些位置恒为 $0$ 或 $-\infty$ ，可以用这个方法减少一点运算。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;

const int N = 2e5 + 5;
using i64 = long long;

int n, m, a[N], b[N];

struct matrix{
    int n, m;
    i64 a[5][5];
    matrix(){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++) a[i][j] = -1e18;
        }
    }
    i64* operator[](int p){ return a[p]; }
};

matrix operator*(matrix a, matrix b){
    matrix c; c.n = a.n, c.m = b.m;
    c[0][0] = 0;
    c[0][1] = max({b[0][1], a[0][1] + b[1][1]});
    c[0][2] = max({b[0][2], a[0][1] + b[1][2], a[0][2]});
    c[0][3] = max({b[0][3], a[0][1] + b[1][3], a[0][2] + b[2][3], a[0][3] + b[3][3]});
    c[0][4] = max({b[0][4], a[0][1] + b[1][4], a[0][2] + b[2][4], a[0][3] + b[3][4], a[0][4]});
    c[1][1] = a[1][1] + b[1][1];
    c[1][2] = max({a[1][1] + b[1][2], a[1][2]});
    c[1][3] = max({a[1][1] + b[1][3], a[1][2] + b[2][3], a[1][3] + b[3][3]});
    c[1][4] = max({a[1][1] + b[1][4], a[1][2] + b[2][4], a[1][3] + b[3][4], a[1][4]});
    c[2][2] = 0;
    c[2][3] = max({b[2][3], a[2][3] + b[3][3]});
    c[2][4] = max({b[2][4], a[2][3] + b[3][4], a[2][4]});
    c[3][3] = a[3][3] + b[3][3];
    c[3][4] = max({a[3][3] + b[3][4], a[3][4]});
    c[4][4] = 0;
    return c;
}

matrix pack(int i){
    matrix res; res.n = res.m = 5;
    res[0][0] = res[2][2] = res[4][4] = 0;
    res[0][1] = res[1][2] = res[2][3] = res[3][4] = a[i] + b[i];
    res[0][2] = res[2][4] = a[i] + 2ll * b[i];
    res[1][1] = res[3][3] = a[i];
    return res;
}

matrix t[N << 2];

void build(int i, int l, int r){
    if(l == r) return t[i] = pack(l), void();
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    t[i] = t[ls] * t[rs];
}

void update(int p, int i, int l, int r){
    if(l == r) return t[i] = pack(p), void();
    int mid = (l + r) >> 1;
    if(p <= mid) update(p, ls, l, mid);
    else update(p, rs, mid + 1, r);
    t[i] = t[ls] * t[rs];
}

matrix query(int ql, int qr, int i, int l, int r){
    if(ql <= l && r <= qr) return t[i];
    int mid = (l + r) >> 1;
    if(ql <= mid && qr > mid) return query(ql, qr, ls, l, mid) * query(ql, qr, rs, mid + 1, r);
    if(ql <= mid) return query(ql, qr, ls, l, mid);
    return query(ql, qr, rs, mid + 1, r);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    build(1, 1, n);
    cin >> m;
    while(m--){
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1) a[x] = y, update(x, 1, 1, n);
        if(op == 2) b[x] = y, update(x, 1, 1, n);
        if(op == 3){
            matrix ret = query(x, y, 1, 1, n);
            matrix tmp; tmp.n = 1, tmp.m = 5;
            tmp[0][0] = 0;
            ret = tmp * ret;
            cout << ret[0][4] << '\n';
        }
    }
    return 0;
}

// Written by xiezheyuan