UVA 10534 Wavio Sequence：最長山脈子序列的 O(n log n) 解法

• 若 x > d[maxLen]，d[++maxLen] = x。
• 否則二分查找第一個 d[pos] >= x，更新 d[pos] = x。
• 當前元素的 LIS 長度即為其插入位置 pos。

C++ 代碼

#include 
using namespace std;
const int MAXN = 10010;
int a[MAXN], lis[MAXN], lds[MAXN], d[MAXN];
int n;

int lowerBound(int *arr, int len, int val) {
    int l = 1, r = len;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (arr[mid] >= val) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

int main() {
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        // 正向 LIS
        int len = 0;
        for (int i = 1; i <= n; ++i) {
            int pos = lowerBound(d, len, a[i]);
            d[pos] = a[i];
            lis[i] = pos;
            if (pos > len) len = pos;
        }
        // 反向 LIS（即原序列 LDS）
        len = 0;
        for (int i = n; i >= 1; --i) {
            int pos = lowerBound(d, len, a[i]);
            d[pos] = a[i];
            lds[i] = pos;
            if (pos > len) len = pos;
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, 2 * min(lis[i], lds[i]) - 1);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n log n)，兩次 LIS 各 O(n log n)。
• 空間：O(n)。

關鍵點總結

1. Wavio 序列本質是「以某點為峰的雙向 LIS」。
2. 峰值處上升與下降長度受限於較短的那側，故取 min。
3. O(n²) DP 會 TLE，必須用 O(n log n) LIS。
4. lower_bound 可用 STL lower_bound(d+1, d+len+1, x) 替換。

總結

本題是「雙向 LIS 組合」的經典應用。掌握 耐心排序法求 LIS 長度並記錄每位置值，可解決 UVA 10534、Codeforces 1010D 等變體題。