题目理解

给定一个长度为 $N$ 的序列 $A$，定义子串 $L$ 的权值为：

​ $VL=min(L)×max(L)×len(L)$

要求计算所有连续子串的权值之和，对 $10^9$ 取模。

数据范围：

$N \leq 5 \times 10^5$

直接枚举所有子串 $O(N^2)$ 不可行

算法思路

这道题采用 分治（CDQ 分治） 的方法，每次取区间中点 $\mathrm{mid}$，计算跨越中点的所有子串的贡献。

对于区间 $[l, r]$，中点 $m = \lfloor (l+r)/2 \rfloor$，跨越 $m$ 的子串 $[i, j]$ 满足 $i \le m < j$。

四种情况

设：

$\mathrm{mn}[i]$ 为 $[i, m]$ 的最小值

$\mathrm{mx}[i]$ 为 $[i, m]$ 的最大值

$\mathrm{mnR}[j]$ 为 $[m+1, j]$ 的最小值

$\mathrm{mxR}[j]$ 为 $[m+1, j]$ 的最大值

对于跨中点的子串 $[i, j]$，其：

$min=min(mn[i],mnR[j])$

$max=max(mx[i],mxR[j])$

长度 $= j - i + 1$

情况 1：LL

左半部分同时控制最小值和最大值

即 $\mathrm{mn}[i] \le \mathrm{mnR}[j]$ 且 $\mathrm{mx}[i] \ge \mathrm{mxR}[j]$

贡献为 $ \mathrm{mn}[i] \times \mathrm{mx}[i] \times \sum_{j} (j-i+1) $

情况 2：RR

右半部分同时控制最小值和最大值

即 $\mathrm{mnR}[j] < \mathrm{mn}[i]$ 且 $\mathrm{mxR}[j] > \mathrm{mx}[i]$

贡献为 $ \mathrm{mnR}[j] \times \mathrm{mxR}[j] \times \sum_{i} (j-i+1) $

情况 3：LR

左半部分控制最小值，右半部分控制最大值

即 $\mathrm{mn}[i] \le \mathrm{mnR}[j]$ 且 $\mathrm{mx}[i] < \mathrm{mxR}[j]$

贡献为 $ \mathrm{mn}[i] \times \mathrm{mxR}[j] \times (j-i+1) $

情况 4：RL

左半部分控制最大值，右半部分控制最小值

即 $\mathrm{mn}[i] > \mathrm{mnR}[j]$ 且 $\mathrm{mx}[i] \ge \mathrm{mxR}[j]$

贡献为 $ \mathrm{mx}[i] \times \mathrm{mnR}[j] \times (j-i+1) $

双指针 + 前缀和优化

对于每种情况，使用双指针维护满足条件的 $j$ 的范围，并用前缀和数组快速计算 $\sum j$ 和 $\sum \mathrm{mxR}[j] \times j$ 等，从而在 $O(\mathrm{len})$ 内完成跨中点计算。

代码结构

$\mathrm{solve}(l, r)$：分治主函数

情况 LL：左端控制 min 和 max

情况 RR：右端控制 min 和 max

情况 LR：左 min 右 max，用 $\mathrm{sum1}$ 和 $\mathrm{sum2}$ 维护右段信息

情况 RL：左 max 右 min，同样用前缀和优化

递归处理左右子区间

复杂度

每层分治 $O(n)$，总 $O(N \log N)$

空间 $O(N)$

总结

这道题是典型的分治统计问题，通过将跨中点子串按最值控制情况分类，并利用双指针和前缀和快速计算贡献，将复杂度从 $O(N^2)$ 降为 $O(N \log N)$，是处理区间最值与子串统计问题的经典方法。