自动搬运

查看原文

来自洛谷，原作者为

	Forge_Unique 这个家伙不懒，忙的没空留下什么东西。||使命，florr玩家

搬运于2025-08-24 23:04:25，当前版本为作者最后更新于2024-10-01 13:55:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

称一个序列 $[b_1, b_2, \dots, b_k]$ 为双调序列（Bitonic Sequence），当且仅当存在一个 $1 \leq i \leq k$ 使得 $b_1 < b_2 < \dots < b_i > \dots > b_k$。

例如，序列 $[1]$，$[2,4,5,7,5,4]$，$[1, 4, 10]$，$[3, 2]$ 都是双调序列，而序列 $[1, 1]$，$[5,4,2,4,5,7]$，$[1,1,4,5,1,4]$ 都不是。

给定一个序列 $[a_1, a_2, \dots, a_n]$。要求计算满足条件的 $(l, r)$ 对的数量，其中 $1 \leq l \leq r \leq n$ 并且序列 $[a_l, a_{l+1}, \dots, a_r]$ 是双调序列。

思路

定义两个数组 $s_i$，$f_i$ 分别表示 $a$ 数组中以 $i$ 为结尾的最长上升子序列和 $a$ 数组中以 $i$ 为开头的最长下降子序列。根据组合数学可知，以 $i$ 为分段处的答案就是 $s_if_i$。而 $s_i$，$f_i$ 这两个数组可以用 $O(n)$ 的时间复杂度递推求出来。所以总时间复杂度为 $O(n)$ 可以通过本题。

代码

code