题意回顾

有 $n$ 个士兵排成一排，技能值为 $a_i$。
要选择若干不相交的长度为 $k$ 的连续区间，最大化技能值总和。
有 $q$ 次询问，每次给定区间 $[l,r]$，求只在该区间内选择的最大总和。

数据范围：$n,q \leq 3\times 10^5$，$k \leq n$。

关键观察

1. 问题转化

选择长度为 $k$ 的不相交区间，相当于在序列上选择一些位置 $i$，使得区间 $[i, i+k-1]$ 不相交，最大化这些区间的和。

设 $s_i = \sum_{j=i}^{i+k-1} a_j$（区间和），则问题转化为：选择不相邻的 $s_i$（因为区间不能重叠），最大化总和。

线段树解法

定义状态

设 $f[i]$ 表示以位置 $i$ 为最后一个区间起点时的最大总和。

则： $f[i] = \max(f[i-1], \max_{j \le i-k} f[j]) + s_i$

维护前缀最大值 $pre[i] = \max_{j \le i} f[j]$，则： $f[i] = \max(f[i-1], pre[i-k]) + s_i$

处理区间查询

对于查询 $[l,r]$，我们只考虑起点在 $[l, r-k+1]$ 的区间。

用线段树维护区间内 $f[i]$ 的最大值，支持区间查询。

最终算法

预处理

1. 计算所有 $s_i = \sum_{j=i}^{i+k-1} a_j$
2. 用前缀和计算：$s_i = prefix[i+k-1] - prefix[i-1]$

在线处理查询

对每个查询 $[l,r]$：

• 有效起点范围：$[L,R] = [l, r-k+1]$
• 如果 $L > R$，答案为 $0$（无法选任何区间）
• 否则用线段树查询 $[L,R]$ 内 $f[i]$ 的最大值

更新策略

从左到右处理位置 $i$：

• 如果 $i < k$：$f[i] = s_i$（只能选一个区间）
• 否则：$f[i] = \max(f[i-1], \max_{j \le i-k} f[j]) + s_i$
• 用线段树维护 $f$ 数组，支持区间最大值查询和单点更新

复杂度分析

• 预处理 $s_i$：$O(n)$
• 线段树建树：$O(n)$
• 每个查询：$O(\log n)$
• 总复杂度：$O(n + q\log n)$，可过 $3\times 10^5$

边界情况

• 当 $k=1$ 时，问题退化为选择若干不相邻的数使和最大
• 当区间长度 $< k$ 时，答案为 $0$
• 所有 $a_i$ 都为负数时，最优解为 $0$（不选任何区间）

总结

本题的核心解法：

1. 将问题转化为选择不相邻的定长区间和
2. 使用动态规划计算最优解
3. 用线段树维护区间最大值以支持任意区间查询
4. 时间复杂度 $O(n + q\log n)$，可处理大规模数据

通过动态规划和数据结构结合，高效解决了带区间约束的最优选择问题。