技巧

调换枚举顺序

Example 1 求

$ans=\sum_{l=1}^{n}\sum_{r=l}^{n}\min_{l\le i\le r}a_i$

求 $\max$ 类似。直接统计十分困难，考虑枚举 $i$，求符合条件的区间数量。

$\begin{aligned} ans&=\sum_{i=1}^{n}\sum_{l=1}^{i}\sum_{r=i}^{n}[a_i=\min_{l\le j\le r}a_j]\\ &=\sum_{i=1}^{n}\sum_{l=1}^{i}\sum_{r=i}^{n}[\forall l\le j\le r,a_i\ge a_j]\\ \end{aligned}$

先假设 $a_i$ 互不相同，那么设 $pre_i$ 为最大的 $j$ 满足 $j<i\land a_j<a_i$，$nxt_i$ 为最小的 $j$ 满足 $j>i\land a_j<a_i$，那么 $l,r$ 必须满足 $pre_i<l\land r<nxt_i$。

不难发现，符合条件的 $[l,r]$ 数量即为 $(i-pre_i)(nxt_i-i)$。故

$ans=\sum_{i=1}^{n}(i-pre_i)(nxt_i-i)$

$pre,nxt$ 可用单调栈求，基本操作。

当 $a_i$ 中有相同元素时可能会算重或算漏，不妨钦定当且仅当 $i$ 为 $[l,r]$ 内第一个最小值时合法，那么需要稍微修改 $pre_i$ 的定义，为最大的 $j$ 满足 $j<i\land a_j\le a_i$，即 $i$ 之前不能有相等的最小值。

Example 2 求

$ans=\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$

其中 $f(l,r)$ 表示 $S(l,r)=\{a_i\mid i\in [l,r]\}$ 中的连续段个数。（Src：AT_abc390_f [ABC390F] Double Sum 3。）

注意到每个连续段必有结尾（或者开头，也是等价的），故使 $[l,r]$ 内每个 $a_x$ 均代表一个连续段，其中 $x$ 满足 $x$ 最小且 $a_x\in S(l,r)\land a_x+1\notin S(l,r)$。

枚举 $x$，求有多少个区间 $[l,r]$ 满足 $S(l,r)$ 中有 $a_x$ 代表的连续段。同样定义 $pre_i$ 为最大的 $j$ 使得 $j<i\land(a_j=a_i\lor a_j=a_i+1)$，$nxt_i$ 为最小的 $j$ 使得 $j>i\land a_j=a_i+1$，答案与上一题形式相同。

Conclusion 本质是将枚举复杂度大的对象换成复杂度小的。比如区间有 $O(n^2)$ 个，而最小值只可能有 $O(n)$ 个，显然枚举最小值更优。但同时也要考虑求合法对应对象的复杂度。最小值求合法区间数量均摊 $O(1)$，可以接受。