「HNOI2016」序列 题解

题目理解

我们有一个长度为 $n$ 的序列 $a[1 \colon n]$，对于每个询问 $[l, r]$，我们需要计算：

即区间 $[l, r]$ 的所有连续子序列的最小值之和。

样例分析： 对于序列 $[5, 2, 4, 1, 3]$，区间 $[1, 3]$ 有6个子序列：

• $[5]$: min = 5
• $[2]$: min = 2
• $[4]$: min = 4
• $[5, 2]$: min = 2
• $[2, 4]$: min = 2
• $[5, 2, 4]$: min = 2

总和 = $5 + 2 + 4 + 2 + 2 + 2 = 17$

问题分析

暴力解法

直接枚举所有子区间，时间复杂度 $O(q \cdot n^2)$，对于 $n, q \leq 10^5$ 不可行。

关键观察

考虑固定右端点 $r$，令 $f(l, r)$ 表示区间 $[l, r]$ 的最小值。当 $r$ 固定时，$f(l, r)$ 关于 $l$ 是单调不减的。

更具体地说，如果我们定义：

• $pre[i]$ = 左边第一个比 $a[i]$ 小的元素位置
• $nxt[i]$ = 右边第一个比 $a[i]$ 小的元素位置

那么对于位置 $i$，它是区间最小值的区间范围是 $(pre[i], i]$ 作为左端点，$[i, nxt[i])$ 作为右端点。

解法思路

方法一：莫队算法 + 单调栈

这是本题的标准解法之一。

预处理：

1. 用单调栈求出每个位置的 $pre[i]$ 和 $nxt[i]$
2. 预处理前缀和数组，用于快速计算贡献

莫队过程：

• 当右指针右移时，新增的贡献可以通过单调性快速计算
• 当左指针左移时，同理计算新增贡献
• 使用适当的数据结构维护当前区间的最小值信息

时间复杂度：$O(n\sqrt{q})$

方法二：离线处理 + 线段树/树状数组

另一种思路是离线处理所有询问，按右端点排序，用线段树维护每个左端点的答案。

算法流程：

1. 将询问按右端点排序
2. 维护一个单调栈，记录当前的最小值变化
3. 用线段树维护每个左端点对应的答案
4. 当右端点移动时，更新受影响的区间

时间复杂度：$O((n+q)\log n)$

方法三：ST表 + 单调栈预处理

这是最高效的解法：

预处理：

1. 建立ST表用于区间最小值查询
2. 用单调栈求出每个位置的 $pre[i]$ 和 $nxt[i]$
3. 预处理：
   • $fl[i]$: 以 $i$ 为右端点的所有区间最小值之和
   • $fr[i]$: 以 $i$ 为左端点的所有区间最小值之和

查询处理： 对于询问 $[l, r]$：

1. 找到区间最小值位置 $p$（用ST表）
2. 答案分成三部分计算：
   • 跨越 $p$ 的区间：贡献为 $a[p] \times (p-l+1) \times (r-p+1)$
   • 左半部分 $[l, p-1]$：用预处理信息计算
   • 右半部分 $[p+1, r]$：用预处理信息计算

时间复杂度：$O(n\log n + q)$

算法复杂度分析

• 预处理：
  • 单调栈：$O(n)$
  • ST表：$O(n\log n)$
  • fl/fr数组：$O(n)$
• 每次查询：$O(1)$
• 总复杂度：$O(n\log n + q)$

关键技巧总结

1. 单调栈的应用：快速求出每个元素作为最小值的影响范围
2. 分治思想：通过区间最小值将问题划分成子问题
3. 前缀和优化：预处理部分和来支持快速查询
4. ST表：高效查询区间最小值位置

这种方法充分利用了区间最小值的性质，将复杂的问题转化为可预处理的形式，从而实现了高效的查询。