题目详细题解

问题重述

给定一个长度为 $n$ 的数组 $a$，表示每条跑道的路段数。
对于每个查询 $(l, u)$，需要选择一个 $r \ge l$，使得完成第 $l$ 到 $r$ 条跑道总共 $k = \sum_{i=l}^r a_i$ 个路段后，能力的总增加量最大。

能力增加规则：
完成第 $1$ 段增加 $u$，第 $2$ 段增加 $u-1$，……，第 $k$ 段增加 $u+1-k$。

因此总增加量为：

$$f(k) = \sum_{j=1}^{k} (u+1-j) = k \cdot u - \frac{k(k-1)}{2} $$

其中 $k = \sum_{i=l}^r a_i$。

---

核心观察

1. $f(k)$ 的性质
   $f(k)$ 是一个关于 $k$ 的二次函数：

   $$f(k) = -\frac{1}{2}k^2 + \left(u + \frac{1}{2}\right)k $$

   它是开口向下的抛物线，对称轴在 $k = u + 0.5$ 附近。
   即：当 $k \le u$ 时，$f(k)$ 随 $k$ 增加而增加；
   当 $k$ 超过 $u$ 很多时，$f(k)$ 会下降。

2. 最优 $k$ 的位置
   由于 $f(k)$ 先增后减，最优的 $k$ 应该在 $u$ 附近。
   具体来说：

   • 如果总路段数 $k \le u$，那么每一段的增加量都是非负的，继续增加路段一定更好。
   • 当 $k > u$ 时，后面会出现负增益，但总增加量可能仍然比 $k \le u$ 时大（例如 $u=5$，$k=6$ 时最后一段 $+0$，总和不减；$k=7$ 时最后一段 $-1$，但前面仍然有 $6$ 段正增益）。

3. 关键结论（来自标程思路）
   对于固定的 $l$ 和 $u$：

   • 找到最大的 $r$，使得总路段数 $k \le u$，记这个 $r$ 为 $r_0$。
   • 最优的 $r$ 只可能在 $r_0$ 或 $r_0+1$（甚至附近小范围）中产生。
   • 更远的 $r$ 由于 $k$ 远大于 $u$，负增益太多，不可能更优。

   为什么？因为 $f(k)$ 在 $k \ge u+1$ 时开始递减，且递减速度加快。
   所以只需要检查 $r_0$ 和 $r_0+1$ 两个候选即可。

   但为了安全（防止边界情况），标程检查了 $r_0$ 附近 $\pm 2$ 的范围。

---

算法步骤

1. 预处理前缀和

设 $ps[i] = \sum_{j=1}^i a_j$，则从 $l$ 到 $r$ 的总路段数为：

$$k = ps[r] - ps[l-1]$$

2. 对于每个查询 $(l, u)$

第一步：二分查找最大的 $r$ 使得 $k \le u$

lb = l, rb = n;
while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    if(ps[mid] - ps[l-1] <= u) 
        lb = mid;
    else 
        rb = mid - 1;
}

这里 $lb$ 就是我们要的 $r_0$。

第二步：在 $r_0$ 附近小范围枚举最优解

检查 $i \in [\max(l, r_0-2), \min(n, r_0+2)]$：

int t = ps[i] - ps[l-1];
int ut = (u + (u - t + 1)) * t / 2;

这里的 ut 计算了 $f(k)$：

$$f(t) = u + (u-1) + \dots + (u-t+1) = \frac{(u + (u-t+1)) \cdot t}{2} $$

这是等差数列求和公式。

第三步：选择 $f(k)$ 最大的 $r$，若相等选最小的 $r$

由于我们按 $i$ 从小到大枚举，当 ut > maxu 时才更新，自然保证了相等时取较小下标。

---

为什么只检查附近几个点？

因为 $f(k)$ 是单峰函数（先增后减），峰值在 $k = u$ 或 $u+1$ 附近。
而 $k$ 只能取前缀和的值，这些值不是连续的，但 $r_0$ 对应最大的 $k \le u$，$r_0+1$ 对应最小的 $k > u$。
最优解一定在这两个 $k$ 对应的 $r$ 中。
再往外，$f(k)$ 只会更小。

检查 $\pm 2$ 是为了处理边界情况（例如 $a_{r_0+1}$ 很大导致 $k$ 跳过 $u$ 较远）。

---

复杂度分析

• 前缀和：$O(n)$
• 每个查询：二分 $O(\log n)$ + 常数次检查
• 总复杂度：$O((n+q)\log n)$，满足题目要求。

---

示例验证（第一个查询）

$a = [3,1,4,1,5,9], l=1, u=8$

• $ps = [0,3,4,8,9,14,23]$
• 二分找到最大的 $r$ 使 $ps[r]-ps[0] \le 8$：$r=3$（$k=8$）
• 检查 $r=2,3,4$：
  • $r=2, k=4$：$f = (8+5)\cdot4/2 = 26$
  • $r=3, k=8$：$f = (8+1)\cdot8/2 = 36$
  • $r=4, k=9$：$f = (8+0)\cdot9/2 = 36$
• 最大值为 $36$，取最小 $r$ → $3$

输出 $3$，与题意一致。

---

总结

这道题的核心是：

1. 将问题转化为二次函数求最值。
2. 利用前缀和快速得到总路段数。
3. 二分找到 $k \le u$ 的最大 $r$。
4. 只在 $r$ 附近检查几个候选点，因为单峰函数的最值就在峰顶附近。

标程的实现非常简洁高效，是典型的 二分 + 数学 题目。