题目解析

我们有两个长度为 $n$ 的数组 $a$ 和 $b$。定义子数组 $[l, r]$ 的代价为：

• 若 $l < r$：代价为 $\sum_{k=l}^r a_k + b_l + b_r$
• 若 $l = r$：代价为 $a_l + 2 \cdot b_l$

我们需要支持三种操作：

1. 单点修改 $a_p$ 的值
2. 单点修改 $b_p$ 的值
3. 查询区间 $[l, r]$ 内两个不相交的非空子数组的最大总代价

---

核心思路

1. 动态规划状态定义

对于单个查询，我们可以用 DP 解决。定义 $dp_{i,k}$ 表示考虑了前 $i$ 个元素，当前状态为 $k$ 时的最大结果。
状态 $k$ 的意义：

• $k = 0$：第一个子数组还未开始
• $k = 1$：第一个子数组已开始，但未结束
• $k = 2$：第一个子数组已结束，第二个子数组未开始
• $k = 3$：第二个子数组已开始，但未结束
• $k = 4$：两个子数组均已结束

转移规则（考虑第 $i$ 个元素）：

对每个当前状态 $k$，我们可以选择：

• 不改变状态（即不把当前元素作为边界），值不变
• 把当前元素作为某个子数组的左边界或右边界，相应增加 $k$ 的值

特殊地，一个元素可以同时作为左边界和右边界（即长度为 $1$ 的子数组），这对应从 $k=0$ 直接到 $k=2$（第一个子数组）或从 $k=2$ 直接到 $k=4$（第二个子数组）。

代价贡献：

• 当 $k$ 为奇数（$1$ 或 $3$）时，表示当前在某个子数组内部，需加上 $a_i$
• 当发生边界转移时，需要加上相应的 $b$ 值：
  • 子数组左边界：加 $b_i$（该位置作为左端点）
  • 子数组右边界：加 $b_i$（该位置作为右端点）
  • 长度为 $1$ 的子数组：加 $2b_i$（同时作为左右边界）

因此，从 $k$ 到 $j$ 的转移，增加的价值为：

• 若 $j = k+1$（左边界）：加 $a_i + b_i$
• 若 $j = k+2$（长度为 $1$ 的子数组）：加 $a_i + 2b_i$
• 若 $j = k$（不选边界）：不加额外值，但若 $k$ 为奇数则仍要加 $a_i$

---

2. 转移矩阵表示

注意到从 $dp_i$ 到 $dp_{i+1}$ 的转移只需要 $5$ 个状态值和当前的 $a_i, b_i$。
我们可以用 $5 \times 5$ 的转移矩阵 $M$ 表示一个元素 $i$ 的影响，其中 $M_{from, to}$ 表示从这个元素开始之前状态为 $from$，到处理完这个元素后状态为 $to$ 的最大收益。

每个元素 $i$ 的初始矩阵 $M_i$ 定义如下：

• 对角线 $M_{0,0} = M_{2,2} = M_{4,4} = 0$
• $M_{0,1} = M_{2,3} = a_i + b_i$（开始一个新子数组）
• $M_{0,2} = M_{2,4} = a_i + 2b_i$（长度为 $1$ 的子数组）
• $M_{1,1} = M_{3,3} = a_i$（在子数组中间）
• $M_{1,2} = M_{3,4} = a_i + b_i$（结束当前子数组）

其余位置为 $-\infty$（表示不可能转移）。

---

3. 矩阵合并

对于两个相邻的元素 $i$ 和 $i+1$，它们的组合效果为矩阵乘法（取 $\max$ 作为加法运算）：

$$(M_i \circ M_{i+1})_{k,j} = \max_{p=0}^{4} (M_i)_{k,p} + (M_{i+1})_{p,j} $$

这实际上是一个（$\max, +$）矩阵乘法，合并的时间复杂度为 $5^3 = 125$，但注意到转移矩阵是上三角形式，实际只需枚举 $0 \le k \le p \le j \le 4$，共 $\binom{5+3}{3} = 35$ 种组合。

---

4. 线段树维护

我们可以用线段树维护区间 $[l, r]$ 的合并矩阵。每个节点存储一个 $5 \times 5$ 的矩阵，表示该区间内所有元素的组合效果。

• 建树：$O(n \cdot 35)$
• 单点修改：更新叶子节点的矩阵，然后向上合并，$O(\log n \cdot 35)$
• 区间查询：查询 $[l, r]$ 的合并矩阵，然后答案即为 $res_{0,4}$（从状态 $0$ 开始，到状态 $4$ 结束的最大总代价），$O(\log n \cdot 35)$

---

5. 时间复杂度

• 单次操作：$O(35 \log n) \approx O(\log n)$
• 总复杂度：$O((n+q) \log n)$，完全满足 $2 \times 10^5$ 的规模

---

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int N = 200'000 + 13;
const int K = 5;
using ll = long long;
using Mat = array<array<ll, K>, K>;

const ll INF = 1e18;

int n, q;
ll a[N], b[N];
Mat tree[4 * N];

Mat init(ll a_val, ll b_val) {
    Mat m;
    forn(i, K) forn(j, i + 1) m[j][i] = -INF;
    m[0][0] = m[2][2] = m[4][4] = 0;
    m[0][1] = m[2][3] = a_val + b_val;
    m[0][2] = m[2][4] = a_val + b_val + b_val;
    m[1][1] = m[3][3] = a_val;
    m[1][2] = m[3][4] = a_val + b_val;
    return m;
}

Mat combine(const Mat& left, const Mat& right) {
    Mat res = init(-INF, -INF);
    forn(k, K) forn(p, k + 1) forn(j, p + 1) {
        res[j][k] = max(res[j][k], left[j][p] + right[p][k]);
    }
    return res;
}

void build(int v, int l, int r) {
    if (l + 1 == r) {
        tree[v] = init(a[l], b[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(v * 2 + 1, l, mid);
    build(v * 2 + 2, mid, r);
    tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
}

void update(int v, int l, int r, int pos) {
    if (l + 1 == r) {
        tree[v] = init(a[l], b[l]);
        return;
    }
    int mid = (l + r) / 2;
    if (pos < mid) update(v * 2 + 1, l, mid, pos);
    else update(v * 2 + 2, mid, r, pos);
    tree[v] = combine(tree[v * 2 + 1], tree[v * 2 + 2]);
}

Mat query(int v, int l, int r, int ql, int qr) {
    if (ql >= r || qr <= l) return init(-INF, -INF);
    if (ql <= l && r <= qr) return tree[v];
    int mid = (l + r) / 2;
    return combine(query(v * 2 + 1, l, mid, ql, qr),
                   query(v * 2 + 2, mid, r, ql, qr));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];

    build(0, 0, n);

    cin >> q;
    forn(_, q) {
        int type, x, y;
        cin >> type >> x >> y;
        --x;
        if (type == 1) {
            a[x] = y;
            update(0, 0, n, x);
        } else if (type == 2) {
            b[x] = y;
            update(0, 0, n, x);
        } else {
            Mat res = query(0, 0, n, x, y);
            cout << res[0][4] << '\n';
        }
    }
    return 0;
}

---

关键点说明

1. 状态设计：$5$ 个状态完美建模了两个不相交子数组的整个过程。
2. 矩阵表示：将 DP 转移抽象为 $5 \times 5$ 矩阵，支持快速合并。
3. 线段树：利用线段树维护区间合并矩阵，支持单点修改和区间查询。
4. 复杂度：每次合并 $35$ 种组合，足够高效。
5. 注意：使用 std::array 而不是 vector 来减少内存开销，矩阵大小固定为 $K \times K$。