题目理解

有一个长度为 $N$ 的数列 $a_i$，以及固定的区间长度 $K$。需要维护所有长度为 $K$ 的连续子数组中，最大值与次大值之和的最大值。并且有 $Q$ 次单点修改，每次修改后需要输出当前答案。

---

关键观察

1. 问题转化

对于每个位置 $i$，我们考虑以 $i$ 为结尾的长度为 $K$ 的区间（即区间 $[i-K+1, i]$），记其最大值和次大值之和为 $f(i)$。那么答案就是所有 $f(i)$ 的最大值。

2. 修改的影响

一次修改 $a_p \gets x$ 只会影响那些包含位置 $p$ 的区间，即满足 $i \in [p, p+K-1]$ 的 $f(i)$。因此每次修改只需要更新 $K$ 个值。

3. 区间查询需求

对于每个区间 $[i-K+1, i]$，我们需要快速查询其最大值和次大值。这可以通过支持区间最大值查询的数据结构实现。

---

算法设计

1. 数据结构设计

主线段树

维护每个位置 $i$ 对应的 $f(i)$（即区间 $[i-K+1, i]$ 的最大值与次大值之和），支持：

• 单点更新 $f(i)$
• 查询全局最大值

辅助线段树

维护原数组 $a$，支持：

• 单点修改 $a_p \gets x$
• 区间最大值查询（用于计算区间的最大值）

2. 算法流程

初始化

1. 建立辅助线段树，存储 $a_i$
2. 对于每个 $i \in [K, N]$，计算区间 $[i-K+1, i]$ 的最大值和次大值
3. 将 $f(i) = mx + smx$ 存入主线段树
4. 输出主线段树的根节点值（全局最大值）

单次修改 $a_p \gets x$

1. 在辅助线段树中更新 $a_p = x$
2. 对于每个 $i \in [p, \min(p+K-1, N)]$：
   • 重新计算区间 $[i-K+1, i]$ 的最大值和次大值
   • 更新主线段树中 $f(i)$ 的值
3. 查询主线段树的全局最大值作为新答案

3. 复杂度分析

时间复杂度

• 初始化：需要计算 $N-K+1$ 个区间，每个区间查询最大值和次大值需要 $O(\log N)$，总复杂度 $O(N \log N)$
• 每次修改：需要更新 $K$ 个区间，每个区间查询需要 $O(\log N)$，总复杂度 $O(K \log N)$
• 总复杂度：$O(N \log N + QK \log N)$

空间复杂度

• 辅助线段树：$O(N)$
• 主线段树：$O(N)$
• 总空间：$O(N)$

---

算法正确性

1. 问题覆盖

每个长度为 $K$ 的连续子数组都对应一个唯一的右端点 $i$，因此通过维护所有 $f(i)$ 可以覆盖所有可能的区间。

2. 修改正确性

由于修改只影响包含该位置的区间，而这些区间恰好对应右端点 $i \in [p, p+K-1]$，因此只需要更新这些 $f(i)$。

3. 查询正确性

辅助线段树可以正确维护区间最大值，通过两次查询（查询最大值，然后排除最大值再查询）可以得到次大值。

---

代码实现要点

1. 数据结构定义

const int N = 1e6 + 5;
int a[N];  // 原数组

struct SegTree {
    int tree[N << 2];
    // ... 建树、更新、查询等操作
} seg;  // 辅助线段树，用于查询区间最大值

struct MainSegTree {
    int tree[N << 2];
    // ... 建树、更新、查询等操作
} mainSeg;  // 主线段树，维护 f(i)

2. 辅助函数

// 计算区间 [l, r] 的最大值和次大值
pair<int, int> query_max_two(int l, int r) {
    int mx = seg.query(l, r);  // 查询最大值
    // 需要排除最大值后查询次大值
    // 实现时可能需要特殊处理
}

3. 初始化流程

void init() {
    // 建立辅助线段树
    seg.build(1, 1, n);
    
    // 计算初始的 f(i)
    for (int i = K; i <= n; i++) {
        auto [mx, smx] = query_max_two(i-K+1, i);
        mainSeg.update(1, 1, n, i, mx + smx);
    }
    
    // 输出初始答案
    cout << mainSeg.query(1, 1, n, K, n) << endl;
}

4. 修改操作

void modify(int p, int x) {
    // 更新原数组和辅助线段树
    a[p] = x;
    seg.update(1, 1, n, p, x);
    
    // 更新受影响的区间
    int L = max(p, K);      // 最小右端点
    int R = min(p+K-1, n);  // 最大右端点
    for (int i = L; i <= R; i++) {
        auto [mx, smx] = query_max_two(i-K+1, i);
        mainSeg.update(1, 1, n, i, mx + smx);
    }
    
    // 输出新答案
    cout << mainSeg.query(1, 1, n, K, n) << endl;
}

---

算法优化

1. 次大值查询优化

查询区间次大值可以通过在辅助线段树中同时维护最大值和次大值来实现，这样可以在 $O(\log N)$ 时间内同时获取两者。

2. 批量更新优化

对于主线段树的更新，可以将连续的 $f(i)$ 更新合并为区间更新，但需要维护区间内最大值的变化。

3. 针对特殊情况的优化

• 当 $K$ 较小时，直接维护每个区间
• 当 $K$ 较大时，考虑使用滑动窗口等数据结构

---

算法标签

• 线段树
• 区间查询
• 分块
• 滑动窗口思想

---

总结

本题的核心在于将问题转化为维护每个右端点对应的区间最大值和次大值之和，并通过线段树高效支持查询和更新。虽然每次修改需要更新 $K$ 个值，但在 $K$ 不是特别大的情况下可以接受。对于更大的数据范围，可能需要更复杂的数据结构优化。