算法标签

• 单调栈
• 动态规划
• 双指针
• 计数

问题分析

双调序列的定义是：存在一个峰值位置 $i$，使得序列在峰值之前严格递增，在峰值之后严格递减。

重要观察：

1. 任何长度为 $1$ 的序列都是双调序列
2. 严格递增序列是双调序列（峰值在末尾）
3. 严格递减序列是双调序列（峰值在开头）
4. 序列中不能有相等的相邻元素（因为要求严格递增/递减）

关键思路

我们可以对每个右端点 $r$，计算有多少个左端点 $l$ 满足 $[l, r]$ 是双调序列。

对于固定的 $r$，有效的 $l$ 需要满足：

• 从 $l$ 到峰值位置是严格递增的
• 从峰值位置到 $r$ 是严格递减的

算法步骤

1. 预处理递增段：

   • 用 inc[i] 表示以 $i$ 结尾的最长严格递增子数组的长度
   • 如果 $a[i] > a[i-1]$，则 inc[i] = inc[i-1] + 1，否则 inc[i] = 1

2. 预处理递减段：

   • 用 dec[i] 表示以 $i$ 开头的最长严格递减子数组的长度
   • 如果 $a[i] > a[i+1]$，则 dec[i] = dec[i+1] + 1，否则 dec[i] = 1

3. 计算双调序列：

   • 对于每个位置 $i$ 作为峰值：
     • 如果它同时是递增段的结尾和递减段的开头，则贡献为 inc[i] * dec[i]
   • 但要避免重复计算，需要仔细处理边界

4. 更高效的方法：

   • 使用双指针，维护当前有效的左端点范围
   • 当加入新元素时，调整左端点范围，保证区间是双调的

时间复杂度

• 最优解法：$O(n)$
• 使用单调栈或双指针技巧

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    long long ans = 0;
    int l = 0;
    
    for (int r = 0; r < n; r++) {
        // 单个元素总是双调序列
        ans++;
        
        if (r > 0) {
            // 处理两个元素的情况
            if (a[r] != a[r-1]) {
                ans++;
            }
            
            // 处理更长的情况
            if (r > 1) {
                if (a[r-2] < a[r-1] && a[r-1] > a[r]) {
                    // 找到峰值，计算以r-1为峰值的双调序列
                    int left = r-1, right = r-1;
                    
                    // 向左扩展严格递增段
                    while (left > l && a[left-1] < a[left]) {
                        left--;
                    }
                    
                    // 向右扩展严格递减段  
                    while (right < n-1 && a[right] > a[right+1]) {
                        right++;
                    }
                    
                    // 计算贡献
                    ans += (r-1 - left + 1) * (right - (r-1) + 1) - 1;
                }
            }
        }
        
        // 更新左边界，跳过不可能成为双调序列的位置
        if (r > 0 && a[r] == a[r-1]) {
            l = r;
        }
    }
    
    cout << ans << endl;
    return 0;
}