一、问题分析与数学建模

1.1 问题本质

这是一道区间查询优化 + 数据结构维护的问题，核心在于巧妙地处理约束条件并高效地维护最优解。

问题形式化

给定：

• 一个长度为 $N$ 的序列 $A[1..N]$
• $Q$ 个查询，每个查询给定区间 $[L, R]$

目标：对于每个查询，在区间 $[L, R]$ 中选择三个位置 $a, b, c$，满足：

1. $L \le a < b < c \le R$（位置严格递增）
2. $b - a \le c - b$（第一次跳跃距离不大于第二次）

使得 $A[a] + A[b] + A[c]$ 最大。

---

1.2 核心数学观察

观察 1：约束条件的等价变换

约束条件 $b - a \le c - b$ 可以改写为：

$$b - a \le c - b \Rightarrow 2b - a \le c \Rightarrow c \ge 2b - a $$

关键启示：对于确定的 $(a, b)$ 配对，第三个起跳点 $c$ 的选择范围是 $[2b - a, R]$。

---

观察 2：枚举策略

朴素算法需要枚举三个位置 $a, b, c$，时间复杂度 $O(N^3 Q)$，不可行。

优化思路：

• 方案1：枚举 $b$，在 $[L, b-1]$ 中选择 $a$，在 $[\max(b+1, 2b-a), R]$ 中选择 $c$

  • 问题：$c$ 的范围依赖于 $a$，难以高效维护

• 方案2：枚举 $c$，维护所有可能的 $(a, b)$ 配对的贡献

  • 关键：当扫描到位置 $c$ 时，哪些 $(a, b)$ 配对变得可行？

---

观察 3：配对的激活条件

对于配对 $(a, b)$（$a < b$），它在位置 $c = 2b - a$ 时首次满足约束条件。

定义：配对 $(a, b)$ 在位置 $c \ge 2b - a$ 时被激活。

动态维护思想：

• 从左到右扫描位置 $c = 1, 2, \ldots, N$
• 当 $c = 2b - a$ 时，激活配对 $(a, b)$
• 维护：对于每个起点 $a$，已激活配对中 $A[a] + A[b]$ 的最大值
• 查询：在区间 $[L, R]$ 内，所有已激活配对的 $A[a] + A[b] + A[c]$ 的最大值

---

观察 4：配对的优化选择

问题：有 $O(N^2)$ 个配对 $(a, b)$，如何高效维护？

关键洞察：不是所有配对都需要考虑！

引理 1：如果存在 $b' \in (a, b)$ 使得 $A[b'] \ge A[b]$，则配对 $(a, b)$ 永远不会是最优解。

证明：

• 考虑配对 $(a, b)$ 和 $(a, b')$
• 激活位置：$c_1 = 2b - a$，$c_2 = 2b' - a$
• 因为 $b' < b$，所以 $c_2 < c_1$
• 配对 $(a, b')$ 更早激活，且 $A[a] + A[b'] \ge A[a] + A[b]$
• 因此配对 $(a, b)$ 劣于 $(a, b')$

推论：对于每个 $a$，只需考虑右边第一个 $A[b] > A[a]$ 的位置 $b$！

同理，对于每个 $b$，只需考虑左边第一个 $A[a] > A[b]$ 的位置 $a$。

---

1.3 单调栈预处理

使用单调栈预处理：

• $l[i]$：位置 $i$ 左边第一个 $A[j] \ge A[i]$ 的位置 $j$
• $r[i]$：位置 $i$ 右边第一个 $A[j] \ge A[i]$ 的位置 $j$

有效配对：只考虑以下两类配对：

1. $(i, r[i])$：$i$ 与右边第一个更大的元素配对
2. $(l[i], i)$：左边第一个更大的元素与 $i$ 配对

配对数量：$O(N)$ 个，而非 $O(N^2)$ 个！

---

二、算法设计：扫描线 + 线段树

2.1 算法框架

扫描线思想：从左到右扫描位置 $c = 1, 2, \ldots, N$。

在扫描到位置 $c$ 时：

1. 激活所有满足 $2b - a = c$ 的配对 $(a, b)$
2. 更新所有位置 $a$ 的可选值（加上 $A[c]$）
3. 回答所有右端点为 $c$ 的查询

---

2.2 线段树维护的信息

对于线段树的每个节点（对应位置 $a$ 的某个区间），维护：

• $\texttt{max1}[a]$：选择 $a$ 作为第一个起跳点时，当前扫描到的所有位置 $c \ge a$ 中 $A[c]$ 的最大值

  形式化：

  $$\texttt{max1}[a] = \max_{c \ge a, c \text{ 已扫描}} A[c] $$

• $\texttt{max2}[a]$：选择 $a$ 作为第一个起跳点时，$A[a] + A[b] + A[c]$ 的最大值

  形式化：

  $$\texttt{max2}[a] = \max_{\substack{a < b < c \\ c \ge 2b - a \\ c \text{ 已扫描}}} (A[a] + A[b] + A[c]) $$

核心思想：

• $\texttt{max1}$ 维护"单点最大值"（对应选择 $c$）
• $\texttt{max2}$ 维护"三点最大和"（对应完整的三段跳）

---

2.3 操作定义

操作 1：区间更新（work）

void work(int k, int v) {
    tree[k].flag = max(tree[k].flag, v);
    tree[k].max2 = max(tree[k].max2, tree[k].max1 + v);
}

含义：将整棵树的所有位置 $a$ 的可选第三个起跳点更新为 $v$。

数学推导：

• 当前扫描到位置 $c$，值为 $A[c] = v$

• 对于任意位置 $a < c$：

  $$\texttt{max1}[a] \leftarrow \max(\texttt{max1}[a], v) $$

• 同时，如果之前已有配对 $(a, b)$ 被激活（$\texttt{max1}[a]$ 已包含某些 $A[b]$ 的贡献），则：

  $$\texttt{max2}[a] \leftarrow \max(\texttt{max2}[a], \texttt{max1}[a] + v) $$

  这里 $\texttt{max1}[a]$ 实际上维护的是 $A[a] + A[b]$ 的最大值（见下文）

懒标记：$\texttt{flag}$ 记录待下推的最大值更新。

---

操作 2：单点更新（cha）

void cha(int k, int x, int v1, int v2) {
    // 在位置 x 更新 max1 为 v1，max2 为 v2
    tree[k].max1 = max(tree[k].max1, v1);
    tree[k].max2 = max(tree[k].max2, v2);
}

含义：激活配对 $(a, b)$ 时，更新位置 $a$ 的信息。

参数含义：

• $x = a$：起点位置
• $v1 = A[a] + A[b]$：前两个起跳点的和
• $v2 = A[a] + A[b] + A[c]$：完整三段跳的值

关键理解：

• 激活配对 $(a, b)$ 时，$c = 2b - a$
• 此时更新 $\texttt{max1}[a] = A[a] + A[b]$
• 同时更新 $\texttt{max2}[a] = A[a] + A[b] + A[c]$

注意：这里 $\texttt{max1}$ 不再只维护"单个 $A[c]$"，而是维护 "$A[a] + A[b]$"。这是因为在激活时，$a$ 和 $b$ 已经确定。

---

操作 3：区间查询（ask）

int ask(int k, int x, int y) {
    // 查询区间 [x, y] 内 max2 的最大值
    return 区间 [x, y] 内所有 max2 的最大值;
}

含义：查询在区间 $[L, R]$ 内选择起点 $a$ 时，三段跳的最大值。

---

2.4 算法流程

// 1. 预处理：单调栈计算 l[] 和 r[]
for (int i = 1; i <= n; i++) {
    while (top && a[st[top]] < a[i])
        top--;
    l[i] = st[top];
    st[++top] = i;
}

// 2. 预处理：计算所有有效配对的激活位置
for (int i = 1; i <= n; i++) {
    if (r[i] <= n) {  // 配对 (i, r[i])
        int c = r[i] - i + r[i];  // c = 2*r[i] - i
        t[c].push_back({i, a[i] + a[r[i]]});
    }
    if (l[i]) {  // 配对 (l[i], i)
        int c = i - l[i] + i;  // c = 2*i - l[i]
        t[c].push_back({l[i], a[l[i]] + a[i]});
    }
}

// 3. 扫描线 + 离线查询
for (int i = 1; i <= n; i++) {
    // 3.1 更新所有位置的可选 c 值
    work(1, a[i]);
    
    // 3.2 激活在位置 i 到达的配对
    for (auto j : t[i]) {
        cha(1, j.x, j.y, j.y + a[i]);
    }
    
    // 3.3 回答右端点为 i 的查询
    for (auto j : qu[i]) {
        ans[j.y] = ask(1, j.x, i);
    }
}

---

三、正确性证明

3.1 单调栈的正确性

引理 2：单调栈正确计算 $l[i]$ 和 $r[i]$。

证明：

• 维护一个单调递减的栈
• 当遇到 $A[i]$ 时，弹出所有 $< A[i]$ 的元素
• 栈顶元素就是左边/右边第一个 $\ge A[i]$ 的位置

---

3.2 配对选择的正确性

引理 3：只考虑 $(i, r[i])$ 和 $(l[i], i)$ 两类配对不会遗漏最优解。

证明： 假设最优解为 $(a, b, c)$。

情况 1：如果 $A[b] \ge A[a]$

• 考虑配对 $(a, b)$
• 如果存在 $b' \in (a, b)$ 使得 $A[b'] \ge A[b]$
  • 则 $(a, b')$ 更优（引理 1）
  • 递归地，最终找到 $b'' = r[a]$（右边第一个更大的）
• 因此 $(a, r[a])$ 至少和 $(a, b)$ 一样好

情况 2：如果 $A[b] < A[a]$

• 类似地，考虑配对 $(l[b], b)$

因此，只考虑这两类配对足够。

---

3.3 线段树维护的正确性

引理 4：扫描到位置 $c$ 时，$\texttt{max2}[a]$ 正确维护了以 $a$ 为起点，$c$ 为终点的最大三段跳值。

证明（归纳法）：

基础：$c = 1$ 时，没有有效的三段跳，$\texttt{max2}[a] = -\infty$，正确。

归纳：假设扫描到 $c - 1$ 时正确，考虑扫描到 $c$：

1. 更新 $\texttt{max1}$：

   $$\texttt{max1}[a] \leftarrow \max(\texttt{max1}[a], A[c]) $$

   此时 $\texttt{max1}[a]$ 维护了所有已扫描位置的最大值。

2. 激活配对： 对于 $c = 2b - a$ 的配对 $(a, b)$：

   $$\texttt{max1}[a] \leftarrow A[a] + A[b]$$ $$\texttt{max2}[a] \leftarrow A[a] + A[b] + A[c]$$

3. 更新 $\texttt{max2}$：

   $$\texttt{max2}[a] \leftarrow \max(\texttt{max2}[a], \texttt{max1}[a] + A[c]) $$
   • 如果 $\texttt{max1}[a]$ 是之前激活的 $A[a] + A[b']$
   • 则 $\texttt{max2}[a]$ 更新为 $A[a] + A[b'] + A[c]$
   • 正确维护了三段跳的最大值

---

3.4 整体正确性

定理：算法正确计算每个查询的答案。

证明：

1. 单调栈正确预处理（引理 2）
2. 配对选择完备（引理 3）
3. 线段树正确维护（引理 4）
4. 离线查询正确回答（扫描到右端点时，所有可能的三段跳都已考虑）

因此算法正确。

---

四、代码模块详解

模块 1：数据结构定义

const int N = 5e5 + 5;
int n, q, top, a[N], l[N], r[N], st[N], ans[N];

struct node {
    int x, y;  // x: 起点位置, y: A[a] + A[b]
};
vector<node> t[N];   // t[c]: 在位置 c 激活的所有配对
vector<node> qu[N];  // qu[r]: 右端点为 r 的所有查询

struct segment {
    int l, r;           // 区间范围
    int max1 = -1e9;    // 维护的第一个最大值
    int max2 = -1e9;    // 维护的第二个最大值
    int flag;           // 懒标记
} tree[N * 4];

设计说明：

• l[i], r[i]：单调栈预处理结果
• t[c]：存储在位置 $c$ 激活的配对，用于扫描线
• qu[r]：离线查询，按右端点分组
• tree：线段树，维护 $\texttt{max1}$ 和 $\texttt{max2}$

---

模块 2：线段树操作

void work(int k, int v) {
    tree[k].flag = max(tree[k].flag, v);
    tree[k].max2 = max(tree[k].max2, tree[k].max1 + v);
}

操作语义：

• 将区间内所有 $\texttt{max1}[a]$ 更新为 $\max(\texttt{max1}[a], v)$
• 同时更新 $\texttt{max2}[a] = \max(\texttt{max2}[a], \texttt{max1}[a] + v)$

数学含义：

• 当扫描到新的位置 $c$，值为 $A[c] = v$
• 所有起点 $a < c$ 都可以选择 $c$ 作为终点
• 更新：$\texttt{max1}[a] \leftarrow \max(\texttt{max1}[a], v)$
• 如果已有配对 $(a, b)$，则 $\texttt{max2}[a] \leftarrow \texttt{max1}[a] + v = A[a] + A[b] + A[c]$

---

void pu(int k) {
    tree[k].max1 = max(tree[k * 2].max1, tree[k * 2 + 1].max1);
    tree[k].max2 = max(tree[k * 2].max2, tree[k * 2 + 1].max2);
}

上传操作：将子节点的最大值合并到父节点。

---

void pd(int k) {
    if (tree[k].flag) {
        work(k * 2, tree[k].flag);
        work(k * 2 + 1, tree[k].flag);
        tree[k].flag = 0;
    }
}

下传操作：将懒标记下推到子节点。

---

void cha(int k, int x, int v1, int v2) {
    if (tree[k].l > x || tree[k].r < x)
        return;
    
    if (tree[k].l == tree[k].r) {
        tree[k].max1 = max(tree[k].max1, v1);
        tree[k].max2 = max(tree[k].max2, v2);
        return;
    }
    
    pd(k);
    cha(k * 2, x, v1, v2);
    cha(k * 2 + 1, x, v1, v2);
    pu(k);
}

单点更新：

• 在位置 $x = a$ 更新值
• $v1 = A[a] + A[b]$：更新 $\texttt{max1}[a]$
• $v2 = A[a] + A[b] + A[c]$：更新 $\texttt{max2}[a]$

调用时机：配对 $(a, b)$ 在位置 $c = 2b - a$ 被激活时。

---

int ask(int k, int x, int y) {
    if (tree[k].l > y || tree[k].r < x)
        return 0;
    
    if (tree[k].l >= x && tree[k].r <= y)
        return tree[k].max2;
    
    pd(k);
    return max(ask(k * 2, x, y), ask(k * 2 + 1, x, y));
}

区间查询：查询区间 $[x, y]$ 内 $\texttt{max2}$ 的最大值。

返回值：在区间 $[x, y]$ 中选择起点 $a$ 时，三段跳的最大值。

---

模块 3：单调栈预处理

// 预处理 l[i]: 左边第一个 >= a[i] 的位置
for (int i = 1; i <= n; i++) {
    while (top && a[st[top]] < a[i])
        top--;
    l[i] = st[top];
    st[++top] = i;
}

// 预处理 r[i]: 右边第一个 >= a[i] 的位置
top = 0;
st[0] = n + 1;
for (int i = n; i >= 1; i--) {
    while (top && a[st[top]] < a[i])
        top--;
    r[i] = st[top];
    st[++top] = i;
}

算法流程：

1. 维护单调递减栈
2. 当前元素 $A[i]$ 弹出所有 $< A[i]$ 的栈顶
3. 剩余栈顶就是左边/右边第一个更大的元素

时间复杂度：每个元素最多入栈出栈一次，$O(N)$。

---

模块 4：配对预处理

for (int i = 1; i <= n; i++) {
    // 配对 (i, r[i])
    if (r[i] <= n && l[r[i]] <= i && r[i] - i + r[i] <= n) {
        t[r[i] - i + r[i]].push_back({i, a[i] + a[r[i]]});
    }
    
    // 配对 (l[i], i)
    if (l[i] && r[l[i]] >= i && i - l[i] + i <= n) {
        t[i - l[i] + i].push_back({l[i], a[l[i]] + a[i]});
    }
}

配对 1：$(i, r[i])$

• $a = i$，$b = r[i]$
• 激活位置：$c = 2b - a = 2 \cdot r[i] - i$
• 存储：$\texttt{t}[c].\texttt{push\_back}(\{i, A[i] + A[r[i]]\})$

配对 2：$(l[i], i)$

• $a = l[i]$，$b = i$
• 激活位置：$c = 2b - a = 2i - l[i]$
• 存储：$\texttt{t}[c].\texttt{push\_back}(\{l[i], A[l[i]] + A[i]\})$

额外检查：

• l[r[i]] <= i：确保 $r[i]$ 左边第一个更大的元素不在 $(i, r[i])$ 之间
• r[l[i]] >= i：确保 $l[i]$ 右边第一个更大的元素不在 $(l[i], i)$ 之间
• 这些检查避免重复配对

时间复杂度：$O(N)$。

---

模块 5：扫描线主循环

for (int i = 1; i <= n; i++) {
    // 1. 更新所有位置的可选 c 值
    work(1, a[i]);
    
    // 2. 激活在位置 i 到达的配对
    for (auto j : t[i]) {
        cha(1, j.x, j.y, j.y + a[i]);
    }
    
    // 3. 回答右端点为 i 的查询
    for (auto j : qu[i]) {
        ans[j.y] = ask(1, j.x, i);
    }
}

步骤解析：

步骤 1：work(1, a[i])

• 含义：将所有位置的 $\texttt{max1}$ 更新为 $\max(\texttt{max1}, A[i])$
• 效果：所有起点 $a < i$ 都可以选择 $c = i$ 作为终点

步骤 2：激活配对

• 对于每个在位置 $i$ 激活的配对 $(a, b)$
• 更新 $\texttt{max1}[a] = A[a] + A[b]$
• 更新 $\texttt{max2}[a] = A[a] + A[b] + A[i]$

步骤 3：回答查询

• 对于右端点为 $i$ 的查询 $[L, i]$
• 查询区间 $[L, i]$ 内 $\texttt{max2}$ 的最大值
• 即在 $[L, i]$ 中选择起点 $a$ 时的最大三段跳值

时间复杂度：

• 步骤 1：$O(\log N)$
• 步骤 2：均摊 $O(N \log N)$（总共 $O(N)$ 个配对）
• 步骤 3：$O(Q \log N)$

---

五、复杂度分析

5.1 时间复杂度

1. 单调栈预处理：$O(N)$

   • 每个元素最多入栈出栈一次

2. 配对预处理：$O(N)$

   • 每个位置最多产生 2 个配对

3. 线段树建树：$O(N)$

4. 扫描线主循环：$O(N \log N + Q \log N)$

   • 外层循环：$O(N)$
   • 每次 work：$O(\log N)$
   • 总共 $N$ 个配对激活：$O(N \log N)$
   • 回答 $Q$ 个查询：$O(Q \log N)$

总时间复杂度：$O(N \log N + Q \log N)$

对于 $N, Q \le 5 \times 10^5$，约为 $10^7$ 次操作，完全可行。

---

5.2 空间复杂度

• 数组：$O(N)$
• 线段树：$O(4N) = O(N)$
• 配对存储：$O(N)$
• 查询存储：$O(Q)$

总空间复杂度：$O(N + Q)$

---

六、算法优化与扩展

6.1 关键优化技巧

1. 单调栈优化配对数量

   • 从 $O(N^2)$ 优化到 $O(N)$
   • 利用了"只需考虑相邻更大元素"的性质

2. 离线查询

   • 避免每次查询都重新计算
   • 按右端点排序，扫描线处理

3. 懒标记

   • 区间更新使用懒标记
   • 降低更新复杂度

4. 一次扫描

   • 同时处理激活、更新、查询
   • 减少常数因子

---

6.2 算法的创新点

传统思路 vs. 本题算法：

传统思路	本题算法
枚举三个位置 $O(N^3)$	扫描线 + 动态维护 $O(N \log N)$
所有配对 $O(N^2)$	单调栈筛选 $O(N)$ 个关键配对
在线查询 $O(QN^3)$	离线查询 $O(Q \log N)$

核心创新：

1. 将约束条件转化为"激活时机"
2. 用单调栈筛选关键配对
3. 线段树同时维护两层信息（$\texttt{max1}$ 和 $\texttt{max2}$）

---

6.3 相关问题与扩展

1. 一般化的多段跳

   • $k$ 段跳：选择 $k$ 个位置，满足跳跃距离递增
   • 可以推广到 $k = 4, 5, \ldots$

2. 不同的约束条件

   • 跳跃距离严格递增：$b - a < c - b$
   • 跳跃距离有上下界：$d_1 \le b - a \le d_2$

3. 动态维护

   • 支持修改某个位置的值
   • 需要动态维护单调栈和线段树

---

七、知识点总结

7.1 核心算法技巧

1. ✅ 单调栈

   • 预处理每个位置的左右最大值
   • 筛选关键配对

2. ✅ 扫描线

   • 从左到右扫描
   • 动态激活配对

3. ✅ 线段树

   • 维护区间最大值
   • 支持区间更新和单点更新
   • 懒标记优化

4. ✅ 离线查询

   • 按右端点分组
   • 减少重复计算

5. ✅ 数学转化

   • 约束条件等价变换
   • 激活条件的推导

---

八、总结

8.1 算法精髓

本题采用的单调栈 + 扫描线 + 线段树算法的核心思想：

1. 问题转化：约束条件 → 激活时机
2. 单调栈筛选：$O(N^2)$ 配对 → $O(N)$ 关键配对
3. 扫描线处理：从左到右动态维护
4. 线段树优化：高效区间更新和查询
5. 离线技巧：按右端点分组，一次扫描完成